[백준] 10026번 적록색약

💡문제접근

• BFS 탐색 알고리즘을 통해 해결할 수 있었다. 적록색약이 아닌 사람의 경우를 먼저 구해준 다음 초록(G)과 빨강(R) 중에서 G → R 혹은 R → G로 바꾼 다음 적록색약인 사람의 경우를 구해 값을 출력했다.

💡코드(메모리 : 34200KB, 시간 : 88ms)

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

N = int(input().strip())
board = [list(map(str, input().strip())) for _ in range(N)]
visited = [[False] * N for _ in range(N)]

normal = 0
abnormal = 0
def BFS(x, y):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True
    while queue:
        x, y = queue.popleft()
        dx = [0, 1, 0, -1]
        dy = [-1, 0, 1, 0]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # board 범위 내에 속해 있어야하고 상하좌우 인접하는 좌표의 색깔이 같으면서 방문하지 않은 좌표의 경우라면?
            if 0 <= nx < N and 0 <= ny < N and board[nx][ny] == board[x][y] and not visited[nx][ny]:
                visited[nx][ny] = True
                queue.append((nx, ny))

for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            BFS(i, j)
            normal += 1

visited = [[False] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if board[i][j] == "R":
            board[i][j] = "G"

for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            BFS(i, j)
            abnormal += 1

print(normal, abnormal)

💡소요시간 : 10m