[탐색/BFS] 백준 10026 적록색약 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

10026번: 적록색약

 

 

 

2. 문제 풀이

 RGB로 구성된 평면에서 색깔별로 나눠진 구역을 구하는 문제입니다. 단, 적록색맹은 녹색과 적색을 구분하지 못해서 동일하게 취급합니다.

 

2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

[Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

 BFS문제입니다. 한 번에 풀려고 고민했으나, 그냥 적록색맹 테이블과 일반 테이블을 구분해서 BFS 탐색하는 게 제일 쉽습니다.

 

 

3. 코드

from collections import deque
import sys
input = sys.stdin.readline

#입력
N = int(input())
ntable = [] #일반 테이블
rgtable = [] #적록색맹 테이블
for _ in range(N):
    x = list(input().rstrip())
    ntable.append(x)
    rgtable.append([1 if i == 'B' else 2 for i in x]) #B는 1, RG는 2로 저장

 일반 테이블과 적록색맹 테이블을 따로 준비합니다.

 적록색맹은 B일 때와 RG일 때 2가지로만 구분합니다.

 

#BFS탐색
def bfs(table, a, b, color):
    direction = [(1,0), (-1,0), (0,1), (0,-1)]
    queue = deque([(a, b)])
    while queue:
        x, y = queue.popleft()
        for dx, dy in direction:
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < N and table[nx][ny] == color:
                queue.append((nx, ny))
                table[nx][ny] = 0

 상하좌우 탐색하고, 탐색된 테이블은 0으로 만듭니다. (따로 visited 테이블을 안 만드셔도 됩니다.)

 

 

cnt = 0 #일반 구역수
cnt_rg = 0 #적록색맹 구역수
for i in range(N):
    for j in range(N):
        if ntable[i][j] != 0:
            cnt += 1
            bfs(ntable, i, j, ntable[i][j])
        if rgtable[i][j] != 0:
            cnt_rg += 1
            bfs(rgtable, i, j, rgtable[i][j])
print(cnt, cnt_rg)

 bfs를 일반 테이블과 적록색맹 테이블 둘 다 탐색합니다. 이후 탐색한 결과를 출력합니다.