[백준/Python] 적록색약 : 10026 / 반례

https://www.acmicpc.net/problem/10026

10026번: 적록색약

 

조건

- 적록색약이 있는 사람과 없는 사람을 띄어쓰기로 구분해서 영역 수 출력

- 적록일 때는 RG를 같은 개체로 생각하도록 하고, 적록이 아닐 경우는 RGB를 다 구분하게 해서 탐색하도록

- 상하좌우만 접근 가능

문제 접근 

1. 미로탐색 같은 문제 : BFS로 풀이

2. 적록색약인 사람인데 , 현재 찾는 기준점 (check)이 RG이고 다음 탐색할 곳이 RG이면 check을 다음 탐색부분으로 바꿔줌

문제풀이

from collections import deque
import sys
input = sys.stdin.readline

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]


def bfs(y, x, check):
    q = deque()
    q.append((y, x))
    c = array[y][x]
    visited[y][x] = True
    while q:
        py, px = q.popleft()
        for index in range(4):
            nx = px + dx[index]
            ny = py + dy[index]
            if nx >= n or nx < 0 or ny >= n or ny < 0:
                continue
            if check == 1 and ((c == 'G' or c == 'R') and (array[ny][nx] == "G" or array[ny][nx] == "R")):
                c = array[ny][nx]
            # check를 통해 적록색약인 사람을 구분 
            # 현재 찾는 기준점(c)이 R or G 이고 다음 탐색할 곳이 R or G이면 현재 찾는 기준점(c)를 변경해줌
            if c == array[ny][nx] and visited[ny][nx] == False:
                visited[ny][nx] = True
                q.append((ny, nx))


# 입력 받음
n = int(input())
array = []
for _ in range(n):
    array.append(list(input().strip()))

area = []
for c in range(0, 2):  # 적록색약이 아닌 경우와 적록색약인 경우
    visited = [[False for _ in range(n)] for _ in range(n)]
    result = 0
    for i in range(n):  # 높이
        for j in range(n):  # 너비
            if visited[i][j] == False:
                bfs(i, j, c)
                result += 1
    area.append(result)

print(str(area[0]) + " " + str(area[1]))

---

잘못된 풀이 (반례는 다 통과되는데 백준은 9프로에서 실패)

def bfs(y, x, check):
    q = deque()
    q.append((y, x))
    c = array[y][x]
    visited[y][x] = True
    while q:
        py, px = q.popleft()
        for index in range(4):
            nx = px + dx[index]
            ny = py + dy[index]
            if nx >= n or nx < 0 or ny >= n or ny < 0:
                continue
            if array[ny][nx] == 'G' and check == 1:  # 적록색약이면 check = 1
                array[ny][nx] = 'R'
            if c == array[ny][nx] and visited[ny][nx] == False:
                visited[ny][nx] = True
                q.append((ny, nx))

array를 직접 바꿔주는 형태로 처음에 풀이를 했었는데 실패했었다.

 

틀린 이유 : 
다음 탐색 위치(array[ny][nx])가 G이고 R로 바뀔 것인데, c(현재 기준점)이 G인 상황에서는 탐색이 되지 않을 것이기에 틀린 코드이다!

---

반례

5
BBBBG
GRBBB
BBBBB
BBBBB
RRRRR

정답: 5 4
출력: 4 3