백준 10026 - 적록색약 (Python3)

코드

import sys
sys.setrecursionlimit(10**5)

n = int(input())
graph = [list(map(str, input())) for _ in range(n)]

# 해당 그리드를 방문하였는가 담을 리스트
visited = [[False] * n for _ in range(n)]

# DFS 실행
def dfs(x, y):
    
    # 상하좌우 방향값
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    # 방문했으면 True
    visited[x][y] = True
    
    # 현재 그리드 색상을 담을 변수
    rgb = graph[x][y]
    
    # 4방향으로 탐색
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        # 범위가 그리디 밖으로 나가지 않으며
        # 방문하지 않은 그리드 중에
        # 색이 같은 그리드를 발견하면 DFS 실행
        if 0 <= nx < n and 0 <= ny < n:
            if not visited[nx][ny]:
                if graph[nx][ny] == rgb:
                    dfs(nx, ny)

# 적록색약 아닌 사람이 볼 수 있는 구역의 개수
answer_1 = 0    

# 적록색약인 사람이 볼 수 있는 구역의 개수
answer_2 = 0

# 적록색약 X
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            dfs(i, j)
            answer_1 += 1

# 적록색약인 사람들의 경우 => G == R로 보임 => 따라서 그냥 두 문자를 통일시키자      
for i in range(n):
    for j in range(n):
        if graph[i][j] == 'G':
            graph[i][j] = 'R'

# 초기화 시켜줘야 이전 경우와 겹치지 않는다.             
visited = [[False] * n for _ in range(n)]       
 
    
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            dfs(i, j)
            answer_2 += 1           
            
print(answer_1, answer_2)     

문제 해설

탐색으로 간단하게 풀 수 있는 문제이다. 사실 나는 방문 여부를 체크할 visited 리스트를 2차원으로 구성하면 간단하게 해결될 것을 어렵게 생각하여 한참 해맸다…

문제의 핵심 요소는 적록색약인 사람들의 경우를 따로 고려해서 문제를 풀어야 하는 점인데, 이는 간단하게 ‘G’ 그리드는 그냥 ‘R’과 같다고 생각하여 ‘R’로 값을 바꿔준 후 탐색을 실행하면 원하는 정답을 쉽게 구할 수 있다.

(DFS로 풀어서 재귀에러 발생 sys.setrecursionlimit(10 ** 5) 필수)