[백준] 10026 적록색약(python 파이썬)

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

10026번: 적록색약

구역의 수를 찾는 문제 근데 이제 색약을 곁들인

dfs나 bfs 중 하나를 택해 문제를 해결하면 된다. 

해결하는 방법이 정말 다양하지만 그중 하나만 작성함.

 

문제 풀이

이 문제는 색약일때와 색약이 아닐 때 각각 어떻게 처리하냐에 풀이가 다를 것이다.

나는 배열을 복사해서 색약일 때(R == G) 따로 함수를 만들어 탐색하도록 만들었다.

 

다른 방법으로는 색약이 아닌 경우 탐색을 해주고

원래 배열에서 R을 G로 변경(또는 G를 R로) 후 탐색을 또 해주면 된다.

 

이미 방문했다는 것을 나타내기 위해 visited 배열을 따로 만들지 않고

그냥 원래 배열에서 문자를 R, G, B가 아닌 다른 문자(Z)로 변경시키는 방법으로 풀었다.

 

전체 코드

import sys
import copy
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
N = int(input())
rg_count = 0
r_count = 0
g_count = 0
b_count = 0

greed = []
for _ in range(N):
    greed.append(list(map(str,input().rstrip())))
rg_greed = copy.deepcopy(greed)

def RedGreenEqual(x,y):
    if x < 0 or x >= N or y < 0 or y >= N:
        return False

    if rg_greed[x][y] == 'R' or rg_greed[x][y] == 'G':
        rg_greed[x][y] = 'Z'
        RedGreenEqual(x + 1, y)
        RedGreenEqual(x - 1, y)
        RedGreenEqual(x, y + 1)
        RedGreenEqual(x, y - 1)
        return True
    return False

def ColorArea(x,y,color):

    if x < 0 or x >= N or y < 0 or y >= N:
        return False

    if greed[x][y] == color:
        greed[x][y] = 'Z'
        ColorArea(x + 1, y, color)
        ColorArea(x - 1, y, color)
        ColorArea(x, y + 1, color)
        ColorArea(x, y - 1, color)
        return True
    return False

for i in range(N):
    for j in range(N):
        if ColorArea(i,j,'R') == True:
            r_count += 1
        if ColorArea(i,j,'G') == True:
            g_count += 1
        if ColorArea(i,j,'B') == True:
            b_count += 1

for i in range(N):
    for j in range(N):
        if RedGreenEqual(i,j) == True:
            rg_count += 1

print(r_count + g_count + b_count, rg_count + b_count)

 

주의할 점은 2차원 배열을 복사할 때 deepcopy로 복사해줘야 한다. 

또한 sys.setrecursionlimit로 재귀 깊이 제한을 늘려줘야 한다.

기존 재귀 깊이(1000)로는 RecursionError뜸.

 

덤으로 추가하면 같은 코드인데 pypy에서는 메모리 초과가 뜬다.

찾아보니까 pypy에서는 재귀에 약하다고 함