Python으로 푸는 백준 10026. 적록색약

백준 10026. 적녹색약

적록색약인 사람은 빨간색과 초록색의 차이를 거의 느끼지 못한다.

따라서, 적록색약인 사람이 보는 그림은 

아닌 사람이 보는 그림과는 조금 다를 수도 있다.

크기가 NxN인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다.

그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다.

적록색약인 사람과 아닌 사람이 보았을 때 그림이 몇 구역으로 보일지 프로그램을 작성하라.

백준에서 푼 문제 리스트 보기

백준에서 문제 보기

github에서 코드 보기(recursion)

github에서 코드 보기(반복문)

문제 풀이

이 문제는 DFS, BFS 관련 백준 대표적인 문제이다. 적록색약인 사람과 그렇지 않은 사람이 보는 구역의 수를 한번에 구하려고 노력하지 않아도 괜찮다. 따로따로 구해도 된다.

이 문제를 풀면서 고민해야 할 부분들인 (1) 재귀로 풀까, 반복문으로 풀까, (2) 적록색약인 사람은 구역을 어떻게 구분할까 (3) 다음 색의 시작점은 어떻게 찾을까 에 대해서 아래에 정리해 두었다. 

재귀로 풀까, 반복문으로 풀까?

DFS, BFS는 재귀로도 풀 수 있지만, 재귀를 사용해서 풀다보면 스택오버플로우로 인해 런타임 에러가 발생할 가능성이 크다. 재귀로 풀 수 있는 모든 코드는 반복문을 사용해서도 문제를 해결할 수 있다.이 문제에서 재귀로 문제를 해결하면 런타임 에러가 난다. 아래와 같이 강제적으로 sys 라이브러리를 호출해 재귀의 한도를 최대치로 올려주면 문제를 풀 수도 있다. 그치만 역시 가장 좋은 방법은 반복문을 사용해 스택오버플로우 날 걱정 없이 문제를 해결하는 것이다. (아래에는 재귀를 활용하여 해결한 방법과 반복문을 활용해 해결한 방법 두가지의 파이썬 코드를 첨부해두었다.)

import sys

sys.setrecursionlimit(100000)  # 강제로 재귀 한도 올리기

적녹색약인 사람일 경우 G, R을 하나로 보게 할 방법이 뭘까?

앞서 말했지만 굳이 한번에 구역의 수를 세도록 풀지 않아도 된다. board(그림)을 두번 순회해서 적녹색약인 사람과 그렇지 않은 사람의 구역의 수를 각각 구하면 된다. 조건문을 줄때 G.R일 경우 같은 색이라고 인식될 수 있도록 조건문을 주거나,  적녹색약인 사람처럼 구역을 세기 전에, baord 자체에서 'G'을 'R'로 바꿔주면 된다.(단, 이 경우에는 O(N*N) 만큼 시간 복잡도가 더해진다) 그러나 코드를 짜기도, 남이 이해하기도 쉽다.

이웃한 같은 색의 지점을 다 찾고나면 다른 색의 시작점을 찾는걸 어떻게 해결할 것인가?

DFS로 탐색했을 때, 같은 색(적녹색약인 사람의 입장에선 동일한 색일 'G', 'R')을 모두 찾고나면, 아직 방문하지 않은 새로운 색의 지점을 찾아야 한다.

첫번째 방법. visited 2차원 배열을 만들어서 방문지점을 미리 표시해두고, 더이상 같은 색이 없을 경우에는 (0,0)에서부터 순회해서 아직 visited하지 않은 지점을 다시 시작점으로 하여 같은 색을 찾아낸다.

두번째 방법. 내 코드처럼 애초에 처음부터 2중 for문으로 visited를 순회하고 있어도 된다. (0,0)부터 이웃한 색을 다 뒤진다음 더이상 while문을 진행할 수 없을 때, 다시 2중 for문으로 돌아와서 그 다음으로 방문하지 않은 visited지점을 찾는다. 이 방법이 효율 상 제일 좋다.

세번째 방법 : visited를 순회하는 노동을 줄이기 위해, 범위를 초과하지 않지만 색이 달라서 visited에 체크하지 않는 경우의 지점을 next_pos에 저장해서 이웃한 지점을 모두 탐색하고나면 next_pos부터 다시 순회하도록 코드를 짜기도 했었다. 그러나 특정한 경우에는 모든 지점을 탐색하지 않는 문제가 발생하기도 하였다. 이 방법은 첫번째 방법과 섞어서 문제를 해결하면 되긴 하지만,  위에 적은 2번째 방법이 코드가 제일 깔끔하고 이해하기가 쉽기 때문에 따로 파이썬 코드를 첨부하진 않겠다.

테스트 예제

백준에는 테스트할 케이스가 너무 적어도 내가 만든 테스크 케이스도 아래에 적어두었다.

10
RRRRRRRRRR
RGGGGGGGGR
RGRRRRRRGR
RGRGGGGRGR
RGRGRRGRGR
RGRGRRGRGR
RGRGGGGRGR
RGRRRRRRGR
RGGGGGGGGR
RRRRRRRRRR

output : 5 1

파이썬 코드 - recursion

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
 
next_color_0 = (0,0)
next_color_1 = (0,0)
color_0_count = 0
color_1_count = 0
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
 
 
def next_pos(visited):
    global n
    for i in range(n):
        for j in range(n):
            if visited[i][j] == -1:
                return (i,j)
    return False
 
def dfs(type, start, end, lines, visited):
    global next_color_0, next_color_1
    global color_0_count, color_1_count
    global dx, dy
 
 
    x, y = start
    # 방문 표시
    visited[x][y] = 1
    if type == 0:
        color_0_count += 1
    elif type == 1:
        color_1_count += 1
 
    current_color = lines[x][y]
 
    for i in range(4):
        temp_x = x + dx[i]
        temp_y = y + dy[i]
 
        if temp_x < 0 or temp_y < 0 or n <= temp_x or n <= temp_y or visited[temp_x][temp_y] != -1:
            continue
 
        next_color = lines[temp_x][temp_y]
 
        # 일반인
        if type == 0:
            if current_color == next_color:
                dfs(0, (temp_x, temp_y), end, lines, visited)
            else:
                next_color_0 = (temp_x, temp_y)
        # 적록색약인 사람
        else:
            if (current_color == next_color) or \
                ((current_color == "G" or current_color == "R") and (next_color == "G" or next_color == "R")):
                dfs(1, (temp_x, temp_y), end, lines, visited)
            else:
                next_color_1 = (temp_x, temp_y)
 
if __name__ == "__main__":
    n = int(input().strip())
    lines = []
    for i in range(n):
        line = list(input().strip())
        lines.append(line)
 
    visited_0 = [[-1]*n for j in range(n)]
    visited_1 = [[-1]*n for j in range(n)]
 
    count_0, count_1 = 0, 0
    while color_0_count < n*n:
        next_x, next_y = next_color_0
        if visited_0[next_x][next_y]:
            next_color_0 = next_pos(visited_0)
        dfs(0, next_color_0, (n-1, n-1), lines, visited_0)
        count_0 += 1
 
    while color_1_count < n*n:
        next_x, next_y = next_color_1
        if visited_1[next_x][next_y]:
            next_color_1 = next_pos(visited_1)
        dfs(1, next_color_1, (n-1, n-1), lines, visited_1)
        count_1 += 1
 
    print("{0} {1}".format(count_0, count_1))

파이썬 코드 - while

import sys
input = sys.stdin.readline
 
 
def dfs(type, pos, board, visited):
    dr = [-1,0,1,0]
    dc = [0,1,0,-1]
    position_list = []
    position_list.append(pos)
    visited[pos[0]][pos[1]] = 1 # 방문 표시
    while position_list:
        r, c = position_list.pop()
        current_color = board[r][c]
 
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr and 0 <= nc and nr < n and nc < n and not visited[nr][nc]:
                next_color = board[nr][nc]
                if current_color == next_color:
                    visited[nr][nc] = 1
                    position_list.append((nr, nc))
                    continue
 
                #적녹 색약인 경우
                if type == 1 and (current_color == 'R' or current_color == "G") \
                            and (next_color == "R" or next_color == "G"):
                    visited[nr][nc] = 1
                    position_list.append((nr, nc))
 
def solve(n, board):
    visited_0 = [[0]*n for j in range(n)]
    visited_1 = [[0]*n for j in range(n)]
    count_0 = 0
    count_1 = 0
    for r in range(n):
        for c in range(n):
            if not visited_1[r][c]:
                dfs(1, (r,c), board, visited_1)
                count_1 += 1
            if not visited_0[r][c]:
                dfs(0, (r,c), board, visited_0)
                count_0 += 1
    print("{0} {1}".format(count_0, count_1))
 
if __name__ == "__main__":
    n = int(input().strip())
    board = []
    for i in range(n):
        board.append(list(input().strip()))
    solve(n, board)
 

#파이썬 백준 10026 #Python 백준 적록색약 #백준 10026. 적록색약