[ BOJ 10026 ] 적록색약 (Python)

문제

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

똑같은 그림을 적록색약인 사람과, 그렇지 않은 사람이 보았을 때 영역의 개수를 구하는 문제다.

" 상하좌우를 체크해서 그래프로 연결하고, 영역의 개수를 구하면 되는거 아닌가? 쉽네~"

이렇게 생각하고 문제를 풀었다가 메모리 초과, 시간 초과, 런타임 에러를 수집했다. 🙃

문제 풀이

처음 내 접근 방식은 아래와 같았다.

1. 색맹 여부에 따라 그래프를 3차원 배열(...)로 만들자
   ➣ graph[x][y][색맹여부]
   ➣ 메모리초과

2. 색맹 여부에 따라 그래프를 따로 만들자
   ➣ two_color_graph, three_color_graph
   ➣ 메모리초과

고민을 하다가 그래프를 따로 구현하지 않고, 함께 쓸 수 있는 방법을 생각해냈다.

1. 우선 적록색맹이 아닐 때 영역의 개수를 구한다.
2. R을 G로 바꿔준다.
3. 적록색맹일 때 영역의 개수를 구한다.

이렇게 간단한 방법이 있는데, 몇시간동안 머리를 끙끙 싸맸다. 으으

코드

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

n = int(input().rstrip())
matrix = [list(input().rstrip()) for _ in range(n)]
visited = [[False] * n for _ in range(n)]

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

def dfs(x,y):
    #현재 색상 좌표를 방문해준다.
    visited[x][y] = True
    current_color = matrix[x][y]

    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if (0 <= nx < n) and (0 <= ny < n):
            #현재 좌표의 색상과 상하좌우 좌표에 있는 색상이 같으면 dfs로 넣어준다.
            if visited[nx][ny]==False:
                if matrix[nx][ny] == current_color:
                    dfs(nx,ny)

for i in range(n):
    for j in range(n):
        # 방문하지 않은 좌표이면 dfs로 넣어준다.
        if visited[i][j]==False:
            dfs(i,j)
            three_cnt += 1

#R을 G로 바꾸어준다. --> 적록색약은 같은 색으로 보기 때문에
for i in range(n):
    for j in range(n):
        if matrix[i][j]=='R':
            matrix[i][j]='G'

visited = [[False] * n for _ in range(n)]

for i in range(n):
    for j in range(n):
        if visited[i][j] == False:
            dfs(i,j)
            two_cnt += 1

print(three_cnt,two_cnt)