10026번 - 적록색약(python3)

문제 링크 : https://www.acmicpc.net/problem/10026

10026번: 적록색약

N*N 그리드에 RGB 색으로 색칠된 그림이 주어집니다. 그림은 색에 따라 구역으로 나뉘어지는데, 같은 색이 상하좌우로 인접해 있을 때 한 구역이라고 인식합니다. 다음은 N=5일 때 R 2구역, G 1구역, B 1구역을 나타내는 예시입니다.

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약인 사람은 빨간색과 초록색의 차이를 거의 느끼지 못합니다. 이 경우에 RorG 2구역, B 1구역으로 인식하게 되겠죠. 위와 같은 그림이 주어졌을 때 적록색약인 사람과 그렇지 않은 사람이 그림을 각각 몇 개의 구역으로 인식하는지 print하면 됩니다.

n = int(input())
pic = []
for _ in range(n): #적록색약이 아닌 사람이 보는 그림(input 그대로)
    pic.append(str(input()))

pic_weak = []
for row in pic: #적록색약인 사람이 보는 그림
    tmp = ['R' if c=='G' else c for c in row]
    pic_weak.append(''.join(tmp))
    

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

def dfs(x,y, pict):
    stack = [[x,y]]
    color = pict[y][x]
    pict[y] = pict[y][:x] + 'X' + pict[y][x+1:]

    while stack:
        a, b = stack.pop()
        for idx in range(4):
            new_x = a + dx[idx]
            new_y = b + dy[idx]
            if 0 <= new_x < n and 0 <= new_y < n and pict[new_y][new_x] == color:
                stack.append([new_x, new_y])
                pict[new_y] = pict[new_y][:new_x] + 'X' + pict[new_y][new_x+1:]

non_weak = 0
for i in range(n): #적록색약이 아닌 경우에 대해 dfs
    for j in range(n):
        if pic[j][i] != 'X':
            dfs(i,j, pic)
            non_weak += 1
weak = 0
for i in range(n): #적록색약일 경우에 대해 dfs
    for j in range(n):
        if pic_weak[j][i] != 'X':
            dfs(i,j, pic_weak)
            weak += 1

print(non_weak, weak)

입력받는 그림은 적록색약이 아닌 사람이 보는 그림인데, 곧이어 바로 적록색약인 사람이 보는 그림을 만들고(G를 R로 치환) 각각에 대해 DFS를 돌렸습니다. 여태까지 구현했던 DFS를 잘 사용하면 어렵지 않게 풀 수 있습니다.