백준 10026 | 적록색약 [파이썬]

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

 

 

풀이

문제 보고 두 가지 해결방안이 떠올랐다.
첫 번째는 주어진 입력으로 적록색약이 아닌 사람이 봤을 때 구역 수를 먼저 구한 뒤에 그리드 내의 R 또는 G를 한 가지 색으로 통일시켜 적록색약인 사람의 구역 수를 구하는 방법
두 번째는 BFS로 돌리면서 현재 색이 R 또는 G 일 때, 상하좌우도 R 또는 G 면 큐에 넣어 구역 수를 구하는 방법
어쨌든 둘 다 적어도 그래프 탐색을 두 번 호출해야 해결할 수 있다.

 

코드

import sys, copy
from collections import deque
sys.setrecursionlimit(10000)
input = sys.stdin.readline

N = int(input())
grid = [list(input().rstrip()) for _ in range(N)]
visited = [[False]*N for _ in range(N)]
wasd = ((0, -1), (0, 1), (-1, 0), (1, 0))

def dfs(x, y, color):
    visited[y][x] = True

    for hx, hy in wasd:
        hx += x
        hy += y

        if (hx >= 0 and hx < N) and (hy >= 0 and hy < N):
            if not visited[hy][hx] and grid[hy][hx] == color:
                dfs(hx, hy, color)

def bfs(blindess):
    queue = deque()
    copy_visited = copy.deepcopy(visited)

    cnt = 0
    for i in range(N):
        for j in range(N):
            if not copy_visited[i][j]:
                queue.append([j, i])
                copy_visited[i][j] = True

                while queue:
                    xx, yy = queue.popleft()

                    for hx, hy in wasd:
                        hx += xx
                        hy += yy

                        if (hx >= 0 and hx < N) and (hy >= 0 and hy < N):
                            if blindess and (not copy_visited[hy][hx]):
                                if grid[yy][xx] == 'G' or grid[yy][xx] == 'R':
                                    if grid[hy][hx] == 'G' or grid[hy][hx] == 'R':
                                        queue.append([hx, hy])
                                        copy_visited[hy][hx] = True
                                else:
                                    if grid[hy][hx] == grid[yy][xx]:
                                        queue.append([hx, hy])
                                        copy_visited[hy][hx] = True
                            else:
                                if not copy_visited[hy][hx] and grid[hy][hx] == grid[yy][xx]:
                                    queue.append([hx, hy])
                                    copy_visited[hy][hx] = True

                cnt += 1

    return cnt

cnt = 0
for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            dfs(j, i, grid[i][j])
            cnt += 1

for i in range(N):
    for j in range(N):
        if grid[i][j] == 'G':
            grid[i][j] = 'R'

visited = [[False]*N for _ in range(N)]
blindcnt = 0
for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            dfs(j, i, grid[i][j])
            blindcnt += 1

print(cnt, blindcnt)

# bfs 정답
# print(bfs(False))
# print(bfs(True))