[#10026] 적록색약

RookieAND·2022년 6월 1일

BFS 백준 코테

BaekJoon

목록 보기

8/42

❓ Question

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

📖 Before Start

너비 탐색인 BFS 적절히 잘 활용해야 하는 문제를 풀어보았다.

이번 문제는 BFS를 사용하여 연결 요소의 갯수를 구하는, 비교적 난이도가 평이한 문제였다.
확실히 단순 탐색의 경우 재귀를 사용하는 DFS 보다는 BFS가 처리 속도 면에서 더 좋아 보인다.

✒️ Design Algorithm

연결 요소를 구하는 문제는 늘 상하좌우 방향을 고려하여 탐색해야 한다.

N * N 이차원 배열 내에 세 가지 종류의 색상 (R, G, B) 가 골고루 포진되어 있는 상태이다.
이 상태에서 정상인이 보았을 때 각 색상 별 연결 요소를 구하여 합을 구하는 것이 첫 번째이며,
적록색약의 경우 빨강색과 초록색의 분간이 불가하기에 동일하다고 판단하여 연결 요소를 구한다.

아래는 필자가 문제를 풀기 전 작성한 알고리즘 설계이다.

정상인의 케이스와 적록색약 환자의 케이스 를 나누어 생각하고, 각각의 연결 요소를 구해보자.

입력 받은 이차원 배열을 deepcopy로 복사하여 새로운 변수에 할당하고, 각 배열을 순회한다.
일반인의 경우 정상적인 BFS 알고리즘을 통해 연결 요소의 수량을 전부 구한다.
적록 색약의 경우 빨강색을 초록색으로 놓고 (편의 상) 연결 요소의 수량을 전부 구한다.

💻 Making Own Code

✅ Correct Code

import copy
import sys
from collections import deque

read = sys.stdin.readline
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]

N = int(read())
picture = [list(read().strip()) for _ in range(N)]
picture_rg = copy.deepcopy(picture)


# 같은 색상을 찾고, 전부 찾았다면 하얀색 (W) 으로 칠한다고 가정.
def bfs(y, x):
    color = picture[y][x]
    picture[y][x] = "W"
    queue = deque([(y, x)])
    while queue:
        ny, nx = queue.popleft()
        for direct in direction:
            my = ny + direct[0]
            mx = nx + direct[1]
            if (0 <= my < N and 0 <= mx < N) and picture[my][mx] == color:
                queue.append((my, mx))
                picture[my][mx] = "W"


# 적록 색약일 경우, R과 G를 동일한 색상이라 가정하고 탐색 진행
def bfs_rg(y, x):
    color = picture_rg[y][x]
    picture_rg[y][x] = "W"
    queue = deque([(y, x)])
    while queue:
        ny, nx = queue.popleft()
        for direct in direction:
            my = ny + direct[0]
            mx = nx + direct[1]
            if 0 <= my < N and 0 <= mx < N:
                # 선택된 색상이 B일 경우에는, 이동된 좌표의 색상도 B여야 함.
                if color == 'B':
                    if picture_rg[my][mx] == 'B':
                        queue.append((my, mx))
                        picture_rg[my][mx] = 'W'
                    continue
                # 선택된 색상이 R, G일 때는 이동된 색상이 B가 아니라면 괜찮음.
                if picture_rg[my][mx] in ['R', 'G']:
                    queue.append((my, mx))
                    picture_rg[my][mx] = 'W'


amount = amount_rg = 0
for i in range(N):
    for j in range(N):
        color_rg = picture_rg[i][j]
        color_normal = picture[i][j]
        # 적록 색약이 아닐 경우, 연결 요소를 파악함.
        if color_normal != 'W':
            bfs(i, j)
            amount += 1
        # 적록 색약일 경우, 연결 요소를 파악함.
        if color_rg != 'W':
            bfs_rg(i, j)
            amount_rg += 1

print(amount, amount_rg)

처음엔 새로운 배열을 복사할 때, R과 G 중 하나를 통일하여 리스트 내 요소를 수정할까도 생각했지만,
1초라는 제한 시간과 다소 적은 128MB의 메모리를 생각하자니 시간 초과 문제에 걸릴 것 같았다.

따라서 이번 문제는 다소 무식한 방법으로 정답을 풀이하였다.
일반인과 적록색약인 사람의 경우를 나누어 각각 다른 함수를 선언하여 BFS 알고리즘 탐색을 진행한 것이다.

상단의 코드에 작성된 BFS_RG 함수의 경우 두 가지 케이스로 접근을 시도하였는데,
첫 번째는 가장 처음 탐색을 시작한 좌표의 색상이 B 일 경우와
두 번째는 가장 처음 탐색을 시작한 좌표의 색상이 R 또는 G 인 경우였다.

그래서 처음 탐색을 시작한 곳의 색상이 B 라면 인접한 색상도 B 여야 큐에 좌표를 추가했고,
반대로 R 혹은 G인 경우, 인접한 색상이 B 만 아니라면 큐에 좌표를 추가하도록 하였다.

✅ Correct Code (other solution)

import copy
import sys
from collections import deque

read = sys.stdin.readline
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]

N = int(read())
picture = [list(read().strip()) for _ in range(N)]
picture_rg = [[0] * N for _ in range(N)]

# 적록색약의 경우, 초록색을 빨간색으로 본다고 가정하고 진행.
for i in range(N):
    for j in range(N):
        picture_rg[i][j] = 'R' if picture[i][j] == 'G' else picture[i][j]


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


# 너비 탐색으로 같은 색상을 찾고, 이를 모두 방문 처리 (visited) 시킴.
def bfs(y, x, graph):
    visited[y][x] = True
    color = graph[i][j]
    queue = deque([(y, x)])
    while queue:
        ny, nx = queue.popleft()
        for direct in direction:
            my = ny + direct[0]
            mx = nx + direct[1]
            # 만약 유효 범위 내에 이동된 좌표가 해당되는지를 판별.
            if 0 <= my < N and 0 <= mx < N:
                # 아직 방문하지 않았고, 동일한 색상이라면 이를 방문 처리 시킴.
                if not visited[my][mx] and graph[my][mx] == color:
                    queue.append((my, mx))
                    visited[my][mx] = True

# 일반 사용자의 케이스를 먼저 조사함.
amount = 0
for i in range(N):
    for j in range(N):
        # 적록 색약이 아닐 경우, 연결 요소를 파악함.
        if not visited[i][j]:
            bfs(i, j, picture)
            amount += 1

# 적록 색약의 케이스를 추가로 조사해야 함.
amount_rg = 0
visited = [[False] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        # 적록 색약이 아닐 경우, 연결 요소를 파악함.
        if not visited[i][j]:
            bfs(i, j, picture_rg)
            amount_rg += 1

print(amount, amount_rg)