[백준] 10026 적록색약

백준 10026 적록색약

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못해 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 다를 수 있다.

크기가 NxN인 그리드 칸에 R, G, B 중 하나를 색칠한 그림이 있다.

그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다.

또한 같은 색상이 상하좌우로 인접해 있느 ㄴ경우에 두 글자는 같은 구역에 속한다.

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

• 첫째 줄: N
• 둘째 줄: 그림의 정보

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력

해결 방식

bfs 탐색을 통해 해결

1. 적록 색약이 아닌 사람이 보는 경우 먼저 탐색
   • visited == 0 인 경우 탐색을 하지 않은 구역 → 탐색 시작
   • 다음 노드를 방문한 적 없고, 현재 노드의 색과 다음 노드의 색이 같은 경우 큐에 추가
   • 한 구역의 조사가 끝나면 count 증가
2. 적록 색약 탐색 시작 전 그래프 변경
   • R값과 G값의 차이를 느끼지 못하므로 R인 구역을 모두 G로 변경
3. 적록 색약의 경우 탐색 시작
   • 1의 경우와 동일

코드

from collections import deque

# 입력
n = int(input())
pictures = [list(input()) for _ in range(n)]

# 그래프 탐색
def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = 1
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0] 

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if visited[nx][ny] == 0 and pictures[x][y] == pictures[nx][ny]:
                visited[nx][ny] = 1
                queue.append((nx, ny))

# 적록 색약이 아닌 경우 먼저 탐색   
count = 0
visited = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if visited[i][j] == 0:
            bfs(i, j)
            count += 1
print(count, end=" ")

# 적록색약의 경우 탐색을 위해 그래프 변형
for i in range(n):
    for j in range(n):
        if pictures[i][j] == "R":
            pictures[i][j] = "G"

# 적록 색약인 경우 탐색
count = 0
visited = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if visited[i][j] == 0:
            bfs(i, j)
            count += 1

print(count)