[백준/python] 10026번: 적록색약

문제

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

10026번: 적록색약

---

문제 요약

크기가 N × N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림을 입력 받는다.

적록색약(빨간색과 초록색을 구분하지 못하는 사람)이 아닌 일반인이 봤을 때,

그림이 몇 개의 구역으로 이루어져 있는지와

적록색약(빨간색과 초록색을 구분하지 못하는 사람)인 사람이 봤을 때,

그림이 몇 개의 구역으로 이루어져 있는지를 출력한다.

 

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

---

코드

import sys
input = __import__('sys').stdin.readline
from collections import deque # 큐

def flood_fill():
    check[i][j] = val 
    q.append((i, j))
    # 방문한 인덱스에 몇번째 구역을 방문했음을 체크하고 큐에 넣는다.
    while q:
        x, y = q.popleft()
        for d in range(4):
            nx, ny = x + dx[d], y + dy[d]
            if 0 <= nx < n and 0 <= ny < n and not check[nx][ny] and color == arr[nx][ny]:
            # 네 방향의 인덱스가 그리드의 범위를 벗어나지 않고
            # 방문하지 않았으며
            # 현재 구역의 색과 같은 색이라면
                check[nx][ny] = val
                # 방문했음을 표시하고
                q.append((nx, ny))
                # 큐에 인덱스를 넣는다.

q = deque() 
# BFS를 진행할 때 사용할 큐

dx, dy = [0, 0, 1, -1], [-1, 1, 0, 0]
# 상하좌우를 탐색 할때 사용할 방향 인덱스

n = int(input())
# 그리드의 크기를 나타낼 정수

arr1 = [list(input().rstrip()) for _ in range(n)]
# 적록색약이 아닌 사람이 보는 그리드

arr2 = [tmp[:] for tmp in arr1] 
# 적록색약인 사람이 보는 그리드로 사용할 2차원 배열
# 2차원 배열을 깊은 복사할 때 주의!! 
# 내부 id값이 같으므로 copy함수를 사용해도 얉은 복사가 된다! (인덱싱 이용)

res = ''
# 결과를 출력할 문자열

for i in range(n):
    for j in range(n):
        if arr2[i][j] == 'G':
            arr2[i][j] = 'R'
# 초록색을 빨간색과 같게 변경

check = [[0] * n for _ in range(n)]
# 그리드를 방문했는지 체크하는 2차원 배열
val = 1
# 인덱스를 방문했을 때 몇번째 구역인지 나타내는 변수
arr = arr1
# 배열이 두 개이므로 먼저 적록색약이 아닌 사람이 보는 그리드를 가리킨다.

for i in range(n):
    for j in range(n):
        if not check[i][j]:
            color = arr[i][j]
            # 현재 방문한 색을 나타내는 color 변수
            flood_fill()
            val += 1
# 방문하지 않은 인덱스가 있다면 BFS를 진행하여 인접한 칸을 val로 채운다.

res += str(val - 1) + ' '
# 결과값에 구역이 몇 개인지 추가

check = [[0] * n for _ in range(n)]
val = 1
# 적록색약의 그리드도 체크해야하므로 리셋
arr = arr2
# 적록색약의 그리드를 가리킨다. (포인터 변경)

for i in range(n):
    for j in range(n):
        if not check[i][j]:
            color = arr[i][j]
            flood_fill()
            val += 1
# 다시 방문하지 않은 인덱스가 있으면 BFS를 진행해 인접한 칸을 val로 채운다.

res += str(val - 1)

print(res)

---

코드 설명

1. 그리드를 입력 받고, 2차원 배열 깊은 복사를 통해 적록색약이 보는 그리드를 생성한다.

 

2. 먼저, 입력 받은 그리드의 인덱스를 하나씩 체크하여 전에 방문하지 않은 인덱스가 있으면 flood_fill 함수를 이용하여 BFS방식으로 인접한 네 방향의 인덱스들도 확인한다. 

+ 만족하는 인덱스가 있으면 큐에 넣고 다시 그 인덱스와 인접한 네 방향의 인덱스들을 확인한다.

 

3. 위 과정이 끝나면 적록색약이 보는 그리드에도 같은 방식으로 몇 개의 구역이 존재하는지 찾는다.

 

4. 결과 값을 출력한다.