[백준 10026번] 적록색약

from collections import deque

n = int(input())

# 영역(2차원 리스트)
area = []

# 적록색약이 아닌 사람의 구역의 수
count_a = 0
# 적록색약인 사람의 구역의 수
count_b = 0

for _ in range(n):
    area.append(list(input()))

# 적록색약 X 방문 여부 2차원 리스트
visited_a = [[False]*n for _ in range(n)]
# 적록색약 O 방문 여부 2차원 리스트
visited_b = [[False]*n for _ in range(n)]

# 적록색약 X BFS함수
def bfs_a(x,y):
    
    if visited_a[x][y]:
        return False
    
    visited_a[x][y] = True
    
    queue = deque([(x,y)])
    
    while queue:
        v = queue.popleft()

        color = area[v[0]][v[1]]
        
        nx = [-1,1,0,0]
        ny = [0,0,-1,1]

        for i in range(4):
            temp_x = v[0] + nx[i]
            temp_y = v[1] + ny[i]
            
            if temp_x >=0 and temp_x < n and temp_y >=0 and temp_y < n and not visited_a[temp_x][temp_y]:
                if color == area[temp_x][temp_y]:
                    queue.append((temp_x,temp_y))
                    visited_a[temp_x][temp_y] = True
                
    
    return True

# 적록색약 O BFS함수
def bfs_b(x,y):
    
    if visited_b[x][y]:
        return False
    
    visited_b[x][y] = True
    
    queue = deque([(x,y)])
    
    while queue:
        v = queue.popleft()

        color = area[v[0]][v[1]]
        
        nx = [-1,1,0,0]
        ny = [0,0,-1,1]

        for i in range(4):
            temp_x = v[0] + nx[i]
            temp_y = v[1] + ny[i]
            
            if temp_x >=0 and temp_x < n and temp_y >=0 and temp_y < n and not visited_b[temp_x][temp_y]:
                if (color=='G' and area[temp_x][temp_y]=='R') or (color == 'R' and area[temp_x][temp_y] == 'G') or color == area[temp_x][temp_y] :
                    queue.append((temp_x,temp_y))
                    visited_b[temp_x][temp_y] = True
    
    return True

for i in range(n):
    for j in range(n):
        if bfs_a(i,j):
            count_a += 1

for i in range(n):
    for j in range(n):
        if bfs_b(i,j):
            count_b += 1


print(count_a,count_b)

이번 문제는 적록색약이 아닌 사람은 색깔(R,G,B)를 구별할 수 있고, 적록색약인 사람은 빨간색(R)과 초록색(G)을 같은 색상으로 인식한다는 가정 하에, 각 색깔로 구분된 영역의 개수를 찾는 문제이다.

 

2차원 리스트로 구성된 영역에서 같은 색깔로 인식되는 영역을 하나씩 탐색하여 개수를 세기 위해서는 탐색 알고리즘을 사용해야 하는데, 이번 문제에서는 BFS를 사용하여 풀어보았다.

 

먼저 적록색약인 사람과 아닌 사람의 기준에서 '방문 여부를 확인하는 2차원 배열'과 '영역의 개수'를 구분(_a, _b)했으며, 나머지는 다음 칸을 체크하는 조건만 다를 뿐, 같은 내용의 BFS 함수이다.

 

BFS 알고리즘의 동작원리와 확인해야 할 조건들을 다시 한번 복습할 수 있었던 문제였다 :)