[Baekjoon/Python] 10026번: 적록색약(BFS)

# Baekjoon 10026번: 적록색약

import sys
sys.setrecursionlimit(10**9)
from collections import deque
input = sys.stdin.readline

N = int(input())
painting = [[] for _ in range(N)]
nor_visited = [[] for _ in range(N)]
abnor_visited = [[] for _ in range(N)]
normal, abnormal = 0, 0

for i in range(N):
    paint = input().rstrip()
    for j in paint:
        painting[i].append(j)
        nor_visited[i].append(0)
        abnor_visited[i].append(0)

def nor_search(x, y):
    if x < 0 or x >= N or y < 0 or y >= N or nor_visited[y][x] == 1:
        return
    else:
        nor_visited[y][x] = 1
        for (tx, ty) in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):
            if 0 <= tx < N and 0 <= ty < N and nor_visited[ty][tx] == 0:
                if painting[y][x] == painting[ty][tx]:
                    nor_search(tx, ty)

def abnor_search(x, y):
    if x < 0 or x >= N or y < 0 or y >= N or abnor_visited[y][x] == 1:
        return
    else:
        abnor_visited[y][x] = 1
        for (tx, ty) in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):
            if 0 <= tx < N and 0 <= ty < N and abnor_visited[ty][tx] == 0:
                if painting[y][x] == 'R' or painting[y][x] == 'G':
                    if painting[ty][tx] == 'R' or painting[ty][tx] == 'G':
                        abnor_search(tx, ty)
                else:
                    if painting[y][x] == painting[ty][tx]:
                        abnor_search(tx, ty)
def BFS():
    global normal, abnormal

    for i in range(N):
        for j in range(N):
            if nor_visited[i][j] == 0:
                nor_search(j, i)
                normal += 1

            if abnor_visited[i][j] == 0:
                abnor_search(j, i)
                abnormal += 1


BFS()
print(normal, abnormal)

 

 이번 문제는 BFS 알고리즘 문제였다. BFS 내부에서 이중 for문을 활용해 nor_visited list와 abnor_visited list에 방문하지 않았을 경우 search 함수를 통해 해당 좌표의 상하좌우를 탐색하도록 구현하였다.

 

 search 함수는 nor_search 함수와 abnor_search 함수로 구분하였다. nor_search 함수는 정상인을 대상으로한 함수이고, abnor_search 함수는 적록색약인 사람을 대상으로한 함수이다.

 

 기본적인 search 함수의 틀은 매개변수로 입력받은 좌표 x, y가 방문하였거나, list의 범위를 초과했을 경우에는 return을, 그렇지 않을 경우에는 visited list에 방문했음을 체크하고(visited[y][x] = 1), for문으로 매개변수의 상하좌우를 모두 탐색하도록한다. 이때도 상하좌우가 list의 범위를 초과하지 않는지와 방문을 했는지를 if문으로 파악해야한다. 파악이 완료됐으면, painting[ty][tx]가 painting[y][x]와 동일한지를 확인한다. 즉, 같은 구역인지를 확인하는 과정이다. 구역이 같은 경우에는 search 함수에 (tx, ty) 좌표를 넣고 탐색을 진행한다.

 

 그럼 nor_search와 abnor_search 함수의 차이에 대해 말해보겠다. abnor_search의 경우에는 nor_search와 비슷하지만 같은 구역인지를 체크하는 부분을 다르게 구현하였다. painting[y][x]가 'R'이거나 'G'인 경우에 painting[ty][tx]도 'R'이거나 'G'이면 같은 구역으로 생각하고 search 함수에 (tx, ty) 좌표를 넣고 탐색을 한다. 만약, painting[y][x]가 'B'인 경우에는 nor_search 함수와 같은 동작을 진행한다.