[BOJ]10026 적록색약

[문제 링크]

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

[풀이]

일반인이 보는 시각, 적록색약이 보는 시각 두 개의 bfs 함수를 만들어 풀었다.

일반인의 경우 현재 위치의 색과 다음 위치의 색이 같을 때만 탐색을 이어나가고 적록색약은 조건을 완화해 R->G 혹은 G->R로도 탐색이 가능하도록 했다.

탐색을 할 때마다 방문 여부를 확인하는 visited 배열을 업데이트해주고 그림 배열(문제에서 주는)을 하나씩 순회하여 해당 칸을 방문하지 않았으면 정답에 1을 더해주었다.

좀 더 짧게 푸는 방법도 있을까 했지만 그냥 무식하게 풀었습니다.

[정답 코드]

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
board = [list(input().strip()) for _ in range(n)]
visited = [[0] * n for _ in range(n)]

ans1 = 0
ans2 = 0

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


def bfs1(r, c): #그냥
    q = deque([[r, c]])
    visited[r][c] = 1
    while q:
        cr, cc = q.popleft()
        for i in range(4):
            nr, nc = cr + dy[i], cc + dx[i]
            if 0 <= nr < n and 0 <= nc < n:
                if board[cr][cc] == board[nr][nc] and not visited[nr][nc]:
                    q.append([nr, nc])
                    visited[nr][nc] = 1


def bfs2(r, c): #적록색약
    q = deque([[r, c]])
    visited[r][c] = 1
    while q:
        cr, cc = q.popleft()
        for i in range(4):
            nr, nc = cr + dy[i], cc + dx[i]
            if 0 <= nr < n and 0 <= nc < n:
                if (
                    board[cr][cc] == board[nr][nc]
                    or board[cr][cc] == "R"
                    and board[nr][nc] == "G"
                    or board[cr][cc] == "G"
                    and board[nr][nc] == "R"
                ) and not visited[nr][nc]:
                    q.append([nr, nc])
                    visited[nr][nc] = 1


for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            ans1 += 1
            bfs1(i, j)

visited = [[0] * n for _ in range(n)]

for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            ans2 += 1
            bfs2(i, j)


print(ans1, end=" ")
print(ans2)