적록색약

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	43773	25116	19348	56.542%

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

예제 입력 1 복사

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

예제 출력 1 복사

4 3

# normal_colormap = copy.deepcopy(color_map)
# abnormal_colormap = copy.deepcopy(color_map)

# for i in range(n):
#     for j in range(n):
#         if normal_colormap[i][j] == 'R':
#             normal_colormap[i][j] = 1
#         elif normal_colormap[i][j] == 'G':
#             normal_colormap[i][j] = 2
#         else :
#             normal_colormap[i][j] = 3

# for i in range(n):
#     for j in range(n):
#         if abnormal_colormap[i][j] == 'B':
#             abnormal_colormap[i][j] = 2        
#         else :
#             abnormal_colormap[i][j] = 1



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

# def dfs(colorMap, nowColor, stack):
#     # if not stack:
#     #     return
#     now_x , now_y = stack.pop()
#     # print(now_x)
#     for i in range(4):
#         next_x = now_x + dx[i]
#         next_y = now_y + dy[i]
#         #범위안에 들어있고
#         # print(next_x)
#         if 0 <= next_x < n and 0 <= next_y < n:
#             # print("hi")
#             if colorMap[next_x][next_y] == nowColor:
#                 colorMap[next_x][next_y] = 0
#                 stack.append((next_x, next_y))
#                 dfs(colorMap, nowColor, stack)
#                 # stack.pop()
#                 # colorMap[next_x][next_y] = nowColor
# # print(color_map)
# def checkmap(colorMap):
#     for i in range(n):
#         for j in range(n):
#             if colorMap[i][j]:
#                 return [colorMap[i][j], i, j]
#     return 0

# cnt = 0
# while True:
#     if checkmap(normal_colormap):
#         nowColor, start_x, start_y  = checkmap(normal_colormap)
#         start = [(start_x, start_y)]
#         dfs(normal_colormap, nowColor, start)
#         cnt += 1
#     else:
#         break


# abcnt = 0
# while True:
#     if checkmap(abnormal_colormap):
#         # print("hi")
#         nowColor, start_x, start_y  = checkmap(abnormal_colormap)
#         start = [(start_x, start_y)]
#         dfs(abnormal_colormap, nowColor, start)
#         abcnt += 1
#     else:
#         break
# print(cnt, end = " ")
# print(abcnt)

첫번째 풀이에서는 시간초과가 나서 해당 DFS로 푸는 코드를 좀 더 시간 복잡도를 생각해서 줄여서 다음과 같은 코드를 작성하였다.

import copy
import sys
sys.setrecursionlimit(10000)

n = int(input())
color_map = [list(input()) for _ in range(n)]
# print(n)
# print(color_map)
color_map2 = copy.deepcopy(color_map)
for i in range(n):
    for j in range(n):
        if color_map2[i][j] == 'R':
            color_map2[i][j] = 'G'

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

def dfs(x, y, color_map):
    now_color = color_map[x][y]
    color_map[x][y] = 0
    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 :
            if color_map[next_x][next_y] == now_color:
                dfs(next_x, next_y, color_map)

cnt = 0            
for i in range(n):
    for j in range(n):
        if color_map[i][j]:
            dfs(i, j , color_map)
            cnt += 1

print(cnt, end=" ")

cnt = 0
for i in range(n):
    for j in range(n):
        if color_map2[i][j]:
            dfs(i, j, color_map2)
            cnt += 1
print(cnt)

처음에 제출했을 때, 시간 초과가 나지 않았지만, 어째서인지 런타임에러가 발생하며, recursion error라고 떴다. 이 에러를 보고 가지치기를 하지 않아서 해당 오류가 발생하는 줄 알았지만 애초에 로직 자체에서 가지치기를 할 방도가 떠오르지 않았다. 계속해서 시간이나 재귀 깊이를 줄이는 방도를 생각하다 방법이 떠오르지 않아서 검색해본 결과,

파이썬은 재귀 깊이가 상당히 얕아 1000이 넘어가면 recursion error로 판단한다는 것을 알았다. 따라서 import sys
sys.setrecursionlimit(10000) 해당 코드 처럼 파이썬에서 재귀 깊이 한계를 조절할 수 있는 라이브러리를 미리 선언해주어야한다.

from collections import deque


def bfs(x, y):
    queue.append((x, y))
    done.append((x, y))
    
    while queue:
        curr = queue.popleft()

        for i in range(4):
            nx = curr[0] + dx[i]
            ny = curr[1] + dy[i]

            if (0 <= nx < N) and (0 <= ny < N) and ((nx, ny) not in done):
                if colors[nx][ny] == colors[curr[0]][curr[1]]:
                    queue.append((nx, ny))
                    done.append((nx, ny))


N = int(input())
colors = [list(input()) for _ in range(N)]

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

# 정상인인 경우
queue = deque()
done = []
cnt_1 = 0

for i in range(N):
    for j in range(N):
        if (i, j) not in done:
            bfs(i, j)
            cnt_1 += 1


# 적록색맹인 경우
for i in range(N):
    for j in range(N):
        if colors[i][j] == 'G':
            colors[i][j] = 'R'

queue = deque()
done = []
cnt_2 = 0
for i in range(N):
    for j in range(N):
        if (i, j) not in done:
            bfs(i, j)
            cnt_2 += 1

print(cnt_1, cnt_2)

그래프 탐색문제이기 때문에 해당 문제는 BFS로도 풀기 가능하다. DFS와 다르게 1자로 길게 있는 형태가 아니라 n * n 형식의 그래프라서 BFS가 훨씬 효율적으로 적용되는 것을 알 수 있었다.

큐를 만든다음, 사방 탐색하면서 아직 방문 안했고(==색깔 확인 안했고) 같은 색인 경우 방문체크 후 큐에 넣었다.

적록색약인 경우는 R과 G가 같으므로 하나의 컬러로 통일 시킨다음 BFS과정을 똑같이 반복했다.

N이 100까지라 이중 for문 여러번 돌려도 상수NN= c*10000 밖에 안되서 시간초과 걱정하지 않아도 된다.

배울점

`sys.setrecursionlimit ...?

[파이썬 코딩테스트 팁]

import sys
sys.setrecursionlimit(10 ** 6)

만약 재귀를 사용해서 풀어야 하는 문제라면, 위 코드를 상단에 쓰는 것은 선택이 아닌 필수이다. 파이썬의 기본 재귀 깊이 제한은 1000으로 매우 얕은 편이다. 따라서 재귀로 문제를 풀 경우 드물지 않게 이 제한에 걸리게 되는데, 문제는 코딩테스트 환경에서는 에러 메시지를 볼 수 없다는 것이다. 이 함정에 걸린 사람은 원인 미상의 런타임 에러를 붙잡고 몇십 분을 각종 테스트케이스를 넣어가며 씨름하겠지만, 그런다고 문제가 잡힐 리 없다. 결국에는 문제를 풀지 못한 채 제출하게 되고 내가 뭘 잘못했지 하는 끝없는 자괴감에 빠지게 되는 것이다.

실제로 올해 여러 번 코딩테스트에 응시하면서 위 코드 없이는 풀 수 없는 문제들을 꽤 많이 봤다. 그중에는 카카오 인턴 코딩테스트 문제도 있었다. 억을하게 문제를 틀리고 싶지 않다면 위 코드를 반드시 숙지해놓아야 할 것이다.