[백준] 10026 적록색약

백준 10026 적록색약

문제 이해하기

1. 각 그림에는 R,G,B의 3가지 색상이 존재한다.
2. 정상인 사람은 R,G,B의 구별이 가능하지만, 적록색약인 사람은 R과 G가 붙어있는 경우 같은 색으로 본다. (떨어져 있는 경우에는 구별 가능)
3. bfs를 이용해 풀 것이다.
4. 정상인 경우 일반적인 bfs 로직을 이용하며 현재 위치의 색상과 주위(4방향)을 탐색하며 같은 색상인 경우에만 visited를 True로 바꿔주고 이동할 수 있도록 하며, 한번의 bfs 연산이 끝났을때 count를 증가시켜 구역의 개수를 세어준다.
5. 적록색약인 경우 일반적인 bfs 로직과 똑같이 진행하지만, R과 G가 붙어있는지 검사하는 조건을 추가해 붙어있다면 이 경우에도 visited를 True로 바꿔주고 이동할 수 있도록한다.

 

풀이

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

dx=[-1,1,0,0]
dy=[0,0,-1,1]

# 정상인 경우
def bfs(x,y):
  q=deque()
  q.append([x,y])
  prevColor=picture[x][y]

  while q:
    x,y=q.popleft()
    prevColor=picture[x][y]

    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]

      if 0<=nx<N and 0<=ny<N and visited[nx][ny]==False:
        if prevColor == picture[nx][ny]:
          visited[nx][ny]=True
          q.append([nx,ny])

# 적록색약인 경우
def blindBfs(x,y):
  q=deque()
  q.append([x,y])
  prevColor=picture[x][y]

  while q:
    x,y=q.popleft()
    prevColor=picture[x][y]

    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]

      if 0<=nx<N and 0<=ny<N and blindVisited[nx][ny]==False:          
        if prevColor == picture[nx][ny] or (prevColor == 'R' and picture[nx][ny] == 'G') or (prevColor == 'G' and picture[nx][ny] == 'R'):
          blindVisited[nx][ny]=True
          q.append([nx,ny])


N=int(input())
picture=[list(map(str, input().rstrip())) for _ in range(N)]
count, blindCount=0, 0

visited=[[False] * N for _ in range(N)]
blindVisited=[[False] * N for _ in range(N)]

for x in range(N):
  for y in range(N):
    if visited[x][y] == False:
      bfs(x, y)
      count+=1

for x in range(N):
  for y in range(N):
    if blindVisited[x][y] == False:
      blindBfs(x, y)
      blindCount+=1

print(count, blindCount)