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

풀이

bfs 연습할 겸 일반 grid, 적록색약 grid2를 순회하는 bfs 2개를 만들어서 풀었다.
q에서 꺼낼 때 방문처리하면 시간초과. append할 때 처리해야 시간초과가 나지 않는다.

코드

import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
grid = [list(map(str, input().strip())) for _ in range(n)]
grid2 = [x[:] for x in grid]
directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
answer1, answer2 = 0, 0
def bfs1(x, y):
    q = deque([(x, y)])
    color = grid[y][x]
    while q:
        x, y = q.popleft()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 > nx or 0 > ny or nx > n - 1 or ny > n - 1:
                continue
            if grid[ny][nx] == color:
                q.append((nx, ny))
                grid[ny][nx] = 0
    return 1

def bfs2(x, y):
    q = deque([(x, y)])
    color = grid2[y][x]
    while q:
        x, y = q.popleft()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 > nx or 0 > ny or nx > n - 1 or ny > n - 1:
                continue
            if color == 'B' and grid2[ny][nx] == 'B':
                q.append((nx, ny))
                grid2[ny][nx] = 0
            elif color == 'G' or color == 'R':
                if grid2[ny][nx] == 'G' or grid2[ny][nx] == 'R':
                    q.append((nx, ny))
                    grid2[ny][nx] = 0
    return 1

for y in range(n):
    for x in range(n):
        if grid[y][x] != 0:
            answer1 += bfs1(x, y)
        if grid2[y][x] != 0:
            answer2 += bfs2(x, y)
print(answer1, answer2)