[Python] 백준 풀기 10026 - 적록색약

파이썬 백준 10026번

골드5

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

10026번: 적록색약

 

 

문제 보기

분류: 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

 

 

 

 

 

문제 풀기

2667번 단지번호붙이기 문제와 비슷하다. 지난번엔 집이 있는 위치를 표시한 숫자 1에 대해 DFS 를 실행하였다면, 이번 문제 적록색약에서는 방문여부에 대해서 그리고 다른 문자 즉 다른 색이 나오는지 까지 확인하여 DFS 를 돌린다.

 

색약이 아닌 경우와 색약인 경우를 분리해서 다뤄야 하는데, 색약이 아닌 경우는 같은 알파벳이 나올때까지 DFS 를 돌리고 다른 알파벳이 나오면 rgb_visited_count += 1 로 카운트롤 올리고 다음 알파벳이 대해 DFS 를 실행한다. 색약일 경우에는 DFS 를 진입하기전에 color_matrix 를 돌려 color_matrix[i][j] == 'R' 이 나오면 'G' 로 문자 변경을 하여 Red 를 Green 으로 바꿔 저장을 하고 GB (GGB) 에 대해서 DFS 를 실행한다.

 

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline
sys.setrecursionlimit(10_001)

def fnRGB_DFS(x, y):
    rgb_visited[x][y] = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < N:
            if color_matrix[nx][ny] == color_matrix[x][y] and rgb_visited[nx][ny] == 0:
                fnRGB_DFS(nx, ny)

def fnGGB_DFS(x, y):
    ggb_visited[x][y] = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < N:
            if color_matrix[nx][ny] == color_matrix[x][y] and ggb_visited[nx][ny] == 0:
                fnGGB_DFS(nx, ny)


if __name__ == "__main__":
    N = int(inputdata().strip())
    color_matrix = [list(map(str, inputdata().strip())) for _ in range(N)]
    # print(color_matrix)         # test print
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    rgb_visited = [[0] * N for _ in range(N)]
    rgb_visited_count = 0
    for i in range(N):
        for j in range(N):
            if rgb_visited[i][j] == 0:
                fnRGB_DFS(i, j)
                rgb_visited_count += 1
    
    for i in range(N):
        for j in range(N):
            if color_matrix[i][j] == 'R':
                color_matrix[i][j] = 'G'
    ggb_visited = [[0] * N for _ in range(N)]
    ggb_visited_count = 0
    for i in range(N):
        for j in range(N):
            if ggb_visited[i][j] == 0:
                fnGGB_DFS(i, j)
                ggb_visited_count += 1
                
                
    print(rgb_visited_count, ggb_visited_count)