[백준/Python] 10026번 적록색약

📌 문제

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

📌 풀이

적록색약을 가지고 있지 않는 사람은 case_1, 적록색약을 가진 사람은 case_2라고 칭한다.

1. (case_1) 각 색깔별 구역 갯수를 저장하기 위해 딕셔너리(color_1)를 생성한다.
2. 인풋으로 받은 그림을 이중리스트(maps)로 만든다.
3. 한번 지나간 컬러를 다시 지나가지 않기 위해 방문여부(chk)를 담는 이중리스트를 만든다.
4. 딕셔너리의 키를 하나씩 가져와 dfs함수를 호출한다.
5. dfs함수로 구한 구역 갯수를 딕셔너리의 밸류 값으로 저장한다.

case_2도 같은 방식으로 거의 같다. 하지만 case_1에 사용한 maps에 변형을 주어야 한다. 적록색약은 빨강과 초록을 구분못하기에 기존의 maps에서 'R'을 'G'로 바꾸거나 'G'을 'R'로 바꾸어야 한다. 이로 인해 빨강과 초록을 하나의 색으로 취급하는 것이다.

풀이 - (성공)

import sys

# 원하는 재귀 깊이로 설정
sys.setrecursionlimit(10000)

n = int(input())
color_1 = {'R':0,'B':0, 'G':0}
color_2 = {'R':0, 'B':0}

maps = [list(input()) for _ in range(n)]
chk = [[False]*n for _ in range(n)]

maps_2 = [[char.replace('G', 'R') for char in row] for row in maps]
chk_2 = [[False]*n for _ in range(n)]


dy=[1,0,-1,0]
dx=[0,1,0,-1]
def dfs(y,x,c,cnt,board,visited):
    for k in range(4):
        ny = y + dy[k]
        nx = x + dx[k]
        if 0<=ny<n and 0<=nx<n:
            if board[ny][nx] == c and visited[ny][nx] == False:
                visited[ny][nx] = True
                dfs(ny,nx,c,cnt,board,visited)

#case_1       
for c in color_1:
    cnt = 0
    for i in range(n):
        for j in range(n):
            if maps[i][j] == c and chk[i][j] == False:
                chk[i][j] = True
                dfs(i,j,c,cnt, maps,chk)
                color_1[c] += 1


#case_2       
for cc in color_2:
    cnt_2 = 0
    for i in range(n):
        for j in range(n):
            if maps_2[i][j] == cc and chk_2[i][j] == False:
                chk_2[i][j] = True
                dfs(i,j,cc,cnt_2,maps_2,chk_2)
                color_2[cc] += 1


print(sum(color_1.values()), sum(color_2.values()))

여기서 잠깐.. 🤚 (알아 두면 좋은 개념)

1️⃣ 런타임 에러 (RecursionError) 방지
DFS로 구현하려면, 재귀를 사용하되, 재귀 깊이를 초과하지 않도록 주의해야 합니다. 재귀 깊이를 제한하는 방법 중 하나는 sys.setrecursionlimit()함수를 사용하는 것이지만, 이 방법은 주의해서 사용해야 합니다. 좀 더 안전한 방법은 반복문을 사용하여 DFS를 구현하는 것입니다.

2️⃣ deepcopy를 사용한 이유
chk를 chk_2에 복사할 때 chk_2 = chk.copy()를 사용하면 안됩니다. (이거 몰라서..한참동안 코드문제를 찾았네요.. ㅠㅠ 만약 사용하게 된다면 case_1의 값은 잘 구해지지만 case_2가 안될거에요..)
copy() 문제가 되는 이유는 해당 메서드가 얕은 복사(shallow copy)를 수행하기 때문입니다!! 얕은 복사는 객체 내부의 내부 객체를 새로 생성하지 않고 원래 객체의 참조를 그대로 사용합니다. 쉽게 말하면 chk_2와 chk는 동일한 내부 리스트를 참조하게 되어 두 리스트가 같은 메모리 공간을 공유하게 되어chk_2를 변경할 때 chk도 변경되므로 원치 않는 결과가 발생합니다. 이런 문제를 해결하려면 깊은 복사(deep copy)를 사용해야 합니다.