백준 10026번: 적록색약 (G5) - Python 풀이

문제 설명

https://www.acmicpc.net/problem/10026

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

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

 

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

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

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100) 둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

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

예제 입력 1

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

예제 출력 1

4 3

풀이 과정

BFS의 심화 문제로, 기본 BFS 구조를 어떻게 바꿔야 해당 문제를 풀 수 있을지 생각해 봐야 하는 문제입니다.

1. 인접한 문자들을 확인하기 위해 dx, dy를 두어 상하좌우 문자들과 비교한다.
2. 인접한 문자가 현재 문자와 같으면 큐에 넣고, 인접한 문자가 현재 문자와 다르면 큐에 넣지 않는다.
3. 큐가 빌 때까지 1,2 로직을 반복한다.
4. 방문하지 않은 좌표에 한해 1,2,3 로직을 반복하면서 반복 횟수 카운트 → 이 횟수가 적록색약이 아닌 사람이 봤을 때의 구역의 개수
5. 이젠 ‘적록색약인 사람’이 봤을 때의 구역을 확인하기 위해 입력값의 R을 G로 대체하고, 방문 여부를 초기화한다.
6. 방문하지 않은 좌표에 한해 1,2,3 로직을 반복하면서 반복 횟수 카운트 → 이 횟수가 적록색약인 사람이 봤을 때의 구역의 개수

정답 코드

# 23:14 ~ 23:55
from collections import deque

N = int(input())
drawing = [[] for _ in range(N)]
visited = [[False for _ in range(N)] for _ in range(N)]

normal = 0
abnormal = 0

for i in range(N):
    drawing[i] = list(input())

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs(x, y):
    queue = deque([(x, y)])
    visited[x][y] = True
    while queue:
        (now_x, now_y) = queue.popleft()
        for d in range(4):
            nx = now_x + dx[d]
            ny = now_y + dy[d]
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny] and drawing[nx][ny] == drawing[x][y]:
                queue.append((nx, ny))
                visited[nx][ny] = True

for x in range(N):
    for y in range(N):
        if not visited[x][y]:
            bfs(x, y)
            normal += 1

visited = [[False for _ in range(N)] for _ in range(N)]

for x in range(N):
    for y in range(N):
        if drawing[x][y] == 'R':
            drawing[x][y] = 'G'

for x in range(N):
    for y in range(N):
        if not visited[x][y]:
            bfs(x, y)
            abnormal += 1

print(normal, abnormal)

포인트 1) drawings의 상하좌우 좌표(= BFS의 인접 노드)를 확인하기 위해 dx, dy 변수 도입.
포인트 2) while queue 내에서 for문을 4번 돌면서 nx, ny 값(= 인접 노드 좌표)을 구하고, 인접 노드의 값이 현재 노드의 값과 같은지를 확인. 같은 경우만 큐에 추가.
포인트 3) 방문되지 않은 (x, y) 좌표일 때에만 bfs 함수를 수행. bfs가 수행된 횟수만큼 normal을 카운트.

혼자서는 절대 못 풀었을 것 같은 꽤 어려운 문제였습니다.
이런 응용 문제도 앞으로 많이 풀어봐야 할 것 같습니다.

이상입니다.