[Baekjoon] 10026. 적록색약(python)

먼저 문제는 다음과 같다. 

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

10026번: 적록색약

풀이

먼저 이 문제는 DFS 문제이다. 다만 적록색약의 경우 빨간색과 초록색을 구별하지 못하기 때문에 DFS를 하기 전 빨간색과 초록색을 한가지 색으로 통일시킨 다음 DFS를 하도록 했다. 즉, 처음에 DFS를 적용하고 그 다음에 색을 통일한 다음 다시 DFS를 하면 해결되는 문제이다. DFS 구현은 recursion 방식으로 하였다. 여기서 중요한 점은 python에 재귀 제한이 걸릴 수 있기 때문에 다음과 같이 코드를 입력하지 않으면 runtime error가 뜰 수 있다.

import sys
sys.setrecursionlimit(int(1e5))

 

 

코드

#파이썬의 경우 재귀 제한이 걸려 있을 수 있기 때문에 다음과 같이 코드를 입력한다.
import sys
sys.setrecursionlimit(int(1e5))

size = int(input())
img = [list(input()) for _ in range(size)]

def dfs(x, y, temp,tag):
    if x <0 or x>=size or y<0 or y>=size or temp[x][y] =='O':
        return False
    if temp[x][y] == tag:
        temp[x][y] = 'O'
        dfs(x-1,y,temp,tag)#left
        dfs(x+1,y,temp,tag)#right
        dfs(x,y-1,temp,tag)#up
        dfs(x,y+1,temp,tag)#down
        return True
    return False
# 깊은 복사
import copy
temp = copy.deepcopy(img)

#보통의 경우
count=0
for i in range(size):
    for j in range(size):
        col = dfs(i,j,temp,temp[i][j])
        if col:
            count +=1
#적록색약의 경우
count2 = 0
for i in range(size):
    for j in range(size):
        if img[i][j] == 'G':
            img[i][j] = 'R'
            

for i in range(size):
    for j in range(size):
        col = dfs(i,j,img,img[i][j])
        if col:
            count2 +=1
    
print(count, count2)