[BOJ/백준] 10026번 적록색약 (Python 파이썬)

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

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

 

---

풀이

우선 문제의 상황을 정리하면 아래와 같습니다.

(1) 일반인
색깔이 다르다면 다른 영역으로 인식한다. 따라서 탐색 가능 여부를 조사할 때 색깔이 일치하는 경우에만 탐색을 진행하는 것으로 한다.

(2) 적록색약
일반인과 유사하게 진행되나, 탐색을 진행하는 지점이 빨간색 or 초록색인 경우 각각 초록색과 빨간색을 탐색 가능 지점으로 인정해 주고 진행한다. (같은 색깔인 경우도 당연히 진행을 허용한다.)
즉, 현재 빨간색 지점을 밣고서 탐색을 4방향으로 실시하고자 탐색 가능 여부를 조사할 때, 빨간색과 초록색 지역은 허용된다는 것이다. 초록색도 마찬가지로 적용된다.

 

저는 이를 위해서 일반인과 적록색약의 경우를 분리해서 각각 (1) 방문 여부 리스트와 (2) BFS 을 따로 구현했습니다.

BFS와 b_BFS의 차이점은 위에서 정리했듯이 색깔로 제한되는 탐색 여부의 조건입니다. 이를 코드로 나타내면 아래와 같습니다.

    while queue:
        x, y = queue.popleft()
        b_visited[y][x] = True
        for i in range(4):
            next_x, next_y = x + dx[i], y + dy[i]
            if 0 <= next_x < N and 0 <= next_y < N and not b_visited[next_y][next_x]:
            
                if graph[next_y][next_x] == color:
                    queue.append([next_x, next_y])
                    b_visited[next_y][next_x] = True
                    
                    # 적록색약의 경우 허용
                elif (color == 'R' and graph[next_y][next_x] == 'G') \
                        or (color == 'G' and graph[next_y][next_x] == 'R'):
                    queue.append([next_x, next_y])
                    b_visited[next_y][next_x] = True

 

따라서, 각각 BFS을 실시하고 구역의 수를 출력하면 풀이가 완료됩니다.

처음에는 하나의 BFS내에서 동작을 구분하여 구현하고 싶었는데, 생각보다 어려웠고 둘을 구분하여도 시간과 메모리가 충분했기 때문에 분리하였습니다!

아래는 최종적인 코드입니다.

Code

import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
graph = [list(input().rstrip()) for _ in range(N)]
visited = [[False for _ in range(N)] for _ in range(N)]
b_visited = [[False for _ in range(N)] for _ in range(N)]

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


def BFS(x, y, color):
    global cnt
    queue = deque([(x, y)])

    while queue:
        x, y = queue.popleft()
        visited[y][x] = True
        for i in range(4):
            next_x, next_y = x + dx[i], y + dy[i]
            if 0 <= next_x < N and 0 <= next_y < N and not visited[next_y][next_x]:
                if graph[next_y][next_x] == color:
                    queue.append([next_x, next_y])
                    visited[next_y][next_x] = True
    cnt += 1


def b_BFS(x, y, color):
    global b_cnt
    queue = deque([(x, y)])

    while queue:
        x, y = queue.popleft()
        b_visited[y][x] = True
        for i in range(4):
            next_x, next_y = x + dx[i], y + dy[i]
            if 0 <= next_x < N and 0 <= next_y < N and not b_visited[next_y][next_x]:
                if graph[next_y][next_x] == color:
                    queue.append([next_x, next_y])
                    b_visited[next_y][next_x] = True
                elif (color == 'R' and graph[next_y][next_x] == 'G') \
                        or (color == 'G' and graph[next_y][next_x] == 'R'):
                    queue.append([next_x, next_y])
                    b_visited[next_y][next_x] = True
    b_cnt += 1


for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            BFS(j, i, graph[i][j])
        if not b_visited[i][j]:
            b_BFS(j, i, graph[i][j])
print(cnt, end=' ')
print(b_cnt, end=' ')