[백준10026번] 적록색약 / Python3

문제

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

크기가 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

나의 풀이

이 문제는 기초적인 문제 풀이는 2583번 영역 구하기와 같은 문제와 똑같다. 해당 문제에서는 적록색약이 있는 경우와 없는 경우를 따로 BFS를 돌려서 영역의 수를 카운트해주면 된다. 기존의 영역 문제들과 다른점이라면 기초적인 영역 구하기 문제는 벽과 벽이 아닌 영역을 나누는 것과 같이 요소가 2가지이지만 해당 문제에서는 'R', 'G', 'B'의 모든 영역을 따져줘야해서 BFS로 해당 영역이 셋 중 어떤 영역인지를 넘겨주어야 했다.

우선 그리드를 입력받고나서 방문여부를 저장하는 그리드와 같은 크기의 배열을 적록색약이 있는 경우와 없는 경우를 나누어 visit_blind, visit_normal로 선언해준다. 또한 영역의 개수를 카운트하기 위한 cnt_blind, cnt_normal을 0으로 초기화해준다. 그리고나서 기존의 영역구하기 문제들과 같이 그리드의 모든 원소를 탐색하기 시작한다. 만약 방문을 하지 않았던 원소라면 BFS를 돌려주는 것 말이다. 그러나 이 문제에서는 적록색약이 있는 경우와 없는 경우를 나누어 확인해야한다. 왜냐하면 적록색약이 있는 사람은 R,G를 하나로 보고 R로 BFS를 돌면서 G도 방문을 해버리기 때문에 나누지 않으면 적록색약이 없는 경우 확인하지 못하는 경우가 생기기 때문이다.

• 적록색약이 있는 경우
  • R, G인 경우
    • BFS를 돌릴때 R,G를 같은 영역으로 봐야함. 따라서 ['R','G']를 넘겨주어 BFS에서 인접한 원소의 값이 넘겨주는 배열에 있는지의 여부를 확인해주면된다.
  • B인 경우
    • ['B']를 넘겨준다.
• 적록색약이 없는 경우
  • 이때에는 위처럼 따로 구분하지 않고 [해당 원소의 값]을 넘겨주어 확인한다.

이렇게 위와 같이 경우를 나누어 BFS를 돌리고 BFS를 돌릴때마다 카운트를 1씩 증가시키면 마지막에는 각각의 영역의 개수를 구할 수 있다.

코드

# 10026번 적록색약
from collections import deque
import sys

# 영역 구분
def check(grid, visit, sep, x, y):
    q = deque()
    q.append([x,y])

    # 상하좌우 인접 가능
    dx = [-1,0,1,0]
    dy = [0,-1,0,1]
    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n:
                if not visit[nx][ny] and grid[nx][ny] in sep:
                    visit[nx][ny] = True
                    q.append([nx,ny])

# main
n = int(input())

grid = []
for _ in range(n):
    grid.append(sys.stdin.readline())

# 각 방문여부를 저장
visit_blind = [[False for _ in range(n)] for _ in range(n)]
visit_normal = [[False for _ in range(n)] for _ in range(n)]

# 영역의 개수를 카운트
cnt_blind = 0
cnt_normal = 0

for i in range(n):
    for j in range(n):
        # 색약인 경우
        if not visit_blind[i][j]:
            visit_blind[i][j] = True
            cnt_blind += 1
            if grid[i][j] == 'B':
                check(grid, visit_blind, ['B'], i, j)
            else:   # 적록을 하나로 보기 위함
                check(grid, visit_blind, ['R', 'G'], i, j)

        # 색약이 아닌 경우
        if not visit_normal[i][j]:
            visit_normal[i][j] = True
            cnt_normal += 1
            check(grid, visit_normal, [grid[i][j]], i, j)

print(cnt_normal, cnt_blind)