[BOJ] 10026. 적록색약(python)

📌문제

💪아이디어

1. 색깔 구별하기
   
   • 적록색약이 있는 사람: 적색/녹색이면 적색과 녹색이 같은 색이라고 확인
   • 색록색약이 없는 사람: RGB모두 구별함
2. 구역 구별하기
   
   • 적록색약이 있는 사람은 적색과 녹색을 같은 색이라고 보기때문에 bfs에서 이미 방문한 곳일 수도 있다.
     
   • 적록색약이 없는 사람은 적색과 녹색을 구별할 수 있기 때문에 방문하지 않을 수 있어 따로 방문체크를 해준다.
     

🥂코드

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

def chk(color,have,y,x):
    if have:
          if not visited_have[y][x]:
            if (color!='B' and grid[y][x]!='B') or (color=='B' and grid[y][x]=='B'): 
               visited_have[y][x]=True
               return True
    else:
       if not visited[y][x] and grid[y][x]==color: 
         visited[y][x]=True
         return True
    return False

def bfs(y,x,color,have):
   queue = deque()
   queue.append((y,x))

   while queue:
      ny,nx = queue.popleft()
      for i in range(4):
        ey,ex = ny + dy[i], nx + dx[i]
        if 0<=ey<n and 0<=ex<n:
           if chk(color,have,ey,ex):
               queue.append((ey,ex))

n = int(input())
grid = []
for _ in range(n):
   grid.append(input().rstrip())

dy = (-1,0,1,0)
dx = (0,1,0,-1)

visited_have = [[False for _ in range(n)]for _ in range(n)]
visited = [[False for _ in range(n)]for _ in range(n)]

answer=[0,0]
for i in range(n):
   for j in range(n):
      color = grid[i][j]

      if not visited[i][j]:
        visited[i][j]=True
        answer[0]+=1
        bfs(i,j,color,False)

      if not visited_have[i][j]:
         visited_have[i][j]=True
         answer[1]+=1
         bfs(i,j,color,True)
print(answer[0],answer[1])