[그래프 순회] 백준 10026: 적록색약

문제: 적록색약은 빨간색과 초록색을 거의 구분하지 못한다. 크기가 N * N인 그리드의 각 칸에 R(빨), G(초), B(파)중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 같은 색상이 상하좌우로 인접해 있는 경우 두 글자는 같은 구역에 속한다.

 

RRRBB

GGBBB

BBBRR

BBRRR

RRRRR

 

위처럼 색상이 나열되어 있을 경우 적록색약이 아닌 사람이 보는 구역의 수는 총 4개이다. 그러나 적록색약인 사람은 R과 G를 거의 같은 색으로 보기 때문에 구역이 3개로 나뉘어져 있다고 보게 된다.

 

그림이 입력으로 주어졌을 때, 적록색약인 사람과 그렇지 않은 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하라.

---

입력: 첫번째 줄에 N, 그 후 N개의 줄에 그림의 배치

---

 

DFS나 BFS를 이용해 풀면 될 것 같다.

많이들 푸는 단지 번호 메기기와 비슷한, 아니 그냥 같은 문제라고 생각한다.

 

답안 코드

import sys
from collections import deque
from copy import deepcopy
sys.stdin = open('10026input.txt')

# 델타 탐색
di = [0, 0, 1, -1]
dj = [1, -1, 0, 0]

def bfs():
    while queue:
        start = queue.popleft()
        for i in range(4):
            ni = start[0] + di[i]
            nj = start[1] + dj[i]
            if 0 <= ni < N and 0 <= nj < N and visited[ni][nj] == 0 and arr[ni][nj] == start[2]: # 다음 탐색할 곳이 범위 안에 있으며 방문하지 않았다면
                queue.append([ni, nj, arr[ni][nj]])
                visited[ni][nj] = 1 # 방문체크 해줘야 다시 안 감

def bfs2():
    while queue2:
        start = queue2.popleft()
        for i in range(4):
            ni = start[0] + di[i]
            nj = start[1] + dj[i]
            if 0 <= ni < N and 0 <= nj < N and visited2[ni][nj] == 0 and arr2[ni][nj] == start[2]: # 다음 탐색할 곳이 범위 안에 있으며 방문하지 않았다면
                queue2.append([ni, nj, arr2[ni][nj]])
                visited2[ni][nj] = 1 # 방문체크 해줘야 다시 안 감

N = int(input())
arr = [] # 그림 원본
for i in range(N):
    arr.append(list(input()))

arr2 = deepcopy(arr) # 적록색약이 보는 그림
for i in range(N):
    for j in range(N):
        if arr2[i][j] == 'G':
            arr2[i][j] = 'R' # 적록색약이 보는 그림을 만들어주자

# bfs 사용
# 너비 우선 탐색임. 어떻게 돌려야 할까?

visited = [[0] * N for _ in range(N)] # 방문기록 체크
visited2 = [[0] * N for _ in range(N)] # 적록색약 방문기록 체크
queue = deque() # 큐
queue2 = deque() # 적록색약 큐
ans_non = 0 # 구획
ans = 0 # 적록색약의 구획

for i in range(N):
    for j in range(N):
        if visited[i][j] == 0: # 아직 방문하지 않았으면 그 점을 기점으로 bfs 돌자
            queue.append([i, j, arr[i][j]])
            ans_non += 1
            bfs()

for i in range(N):
    for j in range(N):
        if visited2[i][j] == 0: # 아직 방문하지 않았으면 그 점을 기점으로 bfs 돌자
            queue2.append([i, j, arr2[i][j]])
            ans += 1
            bfs2()

print(ans_non, ans)

생각나는대로 풀어봤다. 적록색약 버전과 원본 버전을 따로 만들어서 탐색했는데, 만들고 보니 좀 서운하다. 하나의 함수로 돌리는게 나을 것 같다. 그러기 위해선? 간단하다. bfs 함수를 실행시킬 때 매개변수로 arr인지 arr2인지를 넣어주면 된다.

 

이 문제는 bfs의 개념을 리마인드하기 위한 기본적인 문제였다. deque와 deepcopy도 다시 한번 생각해 볼 수 있어 좋았다.

2023. 01. 31