[백준][Python]10026번(적록색약)

백준 10026번

✔️ 문제 풀이

◾ bfs 활용

• 케이스 분리
  1) R과 B와 G를 다른 색으로 인식하는 경우
  2) R과 G를 같은 색, B만 다른 색으로 인식하는 경우
  ⇒ 이 둘을 한 번에 탐색할 수 있는 방법은 없다
• 먼저 한 케이스를 탐색해주고, 이후에 다른 케이스를 탐색해야 한다.
• 두 번째 케이스를 탐색할 때는 큐에 넣는 조건에 R과 G를 같은 색으로 간주하는 부분만 고려해주면 된다.

최종 제출 코드

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

n = int(input().rstrip())
grid = [list(input().rstrip()) for _ in range(n)]
nvisited = [[0]*n for _ in range(n)]
mvisited = [[0]*n for _ in range(n)]
dx = [-1, 1 ,0 ,0]
dy = [0, 0, -1, 1]
q1= deque()
q2= deque()
marea = 0
narea = 0

def bfs1():
  
  while q1:
    x, y = q1.popleft()
    for i in range(4):
      nx = dx[i] + x
      ny = dy[i] + y
      if nx < 0 or nx >= n or ny < 0 or ny >= n:
        continue
      if not nvisited[ny][nx] and grid[ny][nx] == grid[y][x]:
        nvisited[ny][nx] = narea
        q1.append((nx, ny))

def bfs2():
  while q2:
    x, y = q2.popleft()

    for i in range(4):
      nx = dx[i] + x
      ny = dy[i] + y
      if nx < 0 or nx >= n or ny < 0 or ny >= n:
        continue
      if not mvisited[ny][nx] and (grid[ny][nx]==grid[y][x] or grid[ny][nx] in 'RG' and grid[y][x] in 'RG'):
        mvisited[ny][nx] = marea
        q2.append((nx, ny))

for i in range(n):
  for j in range(n):
    if not nvisited[i][j]:
      narea += 1
      q1.append((j, i))
      bfs1()
      
    if not mvisited[i][j]:
      marea += 1
      q2.append((j, i))
      bfs2()

print(narea, marea)

✔️ 실행 결과