백준 10026번 : 적록색약 in Python
이 문제는 빨강, 초록, 파랑으로 색칠한 그림이 주어졌을 때 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 문제이다. 구역이란 어떤 사람이 봤을 때 모두 같은 색으로 이루어진 영역을 말한다.
즉, 적록색약이 아닌 경우에는 빨강, 초록, 파랑을 구별해 같은 색으로 이루어진 구역의 수를 구하는 반면, 적록색약인 경우에는 빨강과 초록을 하나의 색으로 취급해 같은 색으로 이루어진 구역의 수를 구하면 된다.
여러 해결 방법이 있지만, 여기서는 적록색약이 아닌 경우와 적록색약인 경우 각각에 대해 바라본 그림에 대응하는 행렬을 만들어 각 행렬에 그래프 탐색을 이용해 구역의 개수를 구하는 방식으로 문제를 해결한다. 우선 위에서 말한 행렬 두 개를 만든 뒤, input으로 주어진 그림의 각 지점의 색을 조사한다. 이때 파란색에 대응하는 수는 0, 빨간색에 대응하는 수는 1, 초록색에 대응하는 수는 -1이라 하고, 만약 적록색약인 경우에는 빨간색이나 초록색에 대응하는 수를 1로 하자. 이를 바탕으로 그림의 각 지점을 조사하면서 두 행렬의 entry를 채워나간다.
이후 각 지점에 대해 그 지점을 포함하는 구역에 해당하는 모든 지점을 방문하는 함수 DFS를 구현하되 그 지점의 색과 어떤 행렬에 대해 조사하고 있는지를 매개 변수로 추가한다. 그 후 적록색약인 경우와 아닌 경우에 대해 모든 지점을 순회하면서 방문하지 않은 지점에 도달한 경우 구역의 개수를 1 증가시킨 뒤 구역의 모든 지점을 방문하도록 DFS 함수를 해당 지점에 대해 실행한다.
이를 코드로 구현하면 다음과 같다.
import sys
sys.setrecursionlimit(10**5)
N = int(input())
# 적록색약이 아닌 경우 보이는 그림
not_blind_p = [[0]*N for _ in range(N)]
# 적록색약인 경우 보이는 그림
blind_p = [[0]*N for _ in range(N)]
for i in range(N):
s = input()
for j in range(N):
# 파란색은 0, 빨간색은 1, 초록색은 -1에 대응시키되
# 적록색약의 경우 빨간색과 초록색을 1에 대응시킨다.
if s[j] != 'B':
blind_p[i][j] = 1
not_blind_p[i][j] = 1
if s[j] != 'R':
not_blind_p[i][j] = -1
# 매개변수로 어떤 경우에 대한 행렬을 탐색하는지와 해당 지점의 색을 추가한다.
def DFS(x, y, picture, color):
global N
if visited[y][x]: return
visited[y][x] = True
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
for i in range(4):
next_x = x + dx[i]
next_y = y + dy[i]
if 0<=next_x<N and 0<=next_y<N and picture[next_y][next_x] == color:
DFS(next_x, next_y, picture, color)
return
# 적록색약이 아닌 경우 구역의 개수
cnt_not_blind = 0
# 적록색약인 경우 구역의 개수
cnt_blind = 0
visited = [[False]*N for _ in range(N)]
for i in range(N):
for j in range(N):
if not visited[i][j]:
cnt_not_blind += 1
DFS(j, i, not_blind_p, not_blind_p[i][j])
# visited 배열을 다시 초기화한다.
visited = [[False]*N for _ in range(N)]
for i in range(N):
for j in range(N):
if not visited[i][j]:
cnt_blind += 1
DFS(j, i, blind_p, blind_p[i][j])
print(cnt_not_blind, cnt_blind)