[Python] 백준 10026 적록색약

 

문제 분석

• 정사각형 그림
• 그리드 안 r, g, b
• 그림은 몇 개의 구역으로 나뉘어져 있고, 해당 구역은 같은 색으로 이루어져 있다.
• 상하좌우로 인접한 경우 같은 구역 (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상)
• 적록색약은 빨간색(r)과 초록색(g)의 차이를 거의 느끼지 못한다.
• 적록색약 / 아닌 사람이 보는 구역의 수

 

코드 설계

• 적록 색약이 아닌 사람은 r != g
• 적록 색약은 r == g
  
  
• 아직 방문하지 않은 칸이 나오면 덱에 append → 새롭게 찾을 때마다 구역 +1 
• 적록색약 x
  
  • 범위를 벗어나지 않고
  • 아직 방문하지 않고
  • 같은 색이면
    
    
  • 덱에 추가 & 방문 표시
• 적록색약
  • 먄약 현재 색이 B이면 : B가 아닌 색으로는 갈 수 x
  • 현재 색이 R or G 이라면 B인 경우에만 갈 수 없다.

 

정답 코드

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

n = int(input())
g = [list(input().strip()) for _ in range(n)]

v_nor = [[False] * n for _ in range(n)]
v_blind = [[False] * n for _ in range(n)]

# 이동방향 - 상하좌우
dh = [-1, 1, 0, 0]
dw = [0, 0, -1, 1]

d_nor = deque()
d_blind = deque()
zone_nor = 0
zone_blind = 0

# 적록색약 x
for i in range(n) :
    for j in range(n) :
        if not v_nor[i][j] : # 아직 방문하지 않은 이전과 다른 색을 찾으면
            d_nor.append((i,j))
            v_nor[i][j] = True
            zone_nor += 1

        while d_nor : # 같은 색 찾기
            h, w = d_nor.popleft()
            now_color = g[h][w] # 현재 색깔

            for k in range(4) :
                nh = h + dh[k]
                nw = w + dw[k]

                if nh < 0 or nh >= n or nw < 0 or nw >= n :
                    continue
                if v_nor[nh][nw] :
                    continue
                if g[nh][nw] != now_color :
                    continue

                d_nor.append((nh, nw))
                v_nor[nh][nw] = True

# 적록 색약
for i in range(n) :
    for j in range(n) :
        if not v_blind[i][j] :
            d_blind.append((i,j))
            v_blind[i][j] = True
            zone_blind += 1  # 새로운 색을 찾으면

        while d_blind :
            h, w = d_blind.popleft()
            now_color = g[h][w]

            for k in range(4) :
                nh = h + dh[k]
                nw = w + dw[k]

                if nh < 0 or nh >= n or nw <0 or nw >= n :
                    continue
                if v_blind[nh][nw] :
                    continue

                # '현재 색이 파랑색일 때는 다른 색으로 볼 수 없다.
                if now_color == 'B' :
                    if g[nh][nw] != 'B' :
                        continue
                # 현재 색이 빨강 or 초록일 때 파랑이 아니면 된다.
                if now_color == 'R' :
                    if g[nh][nw] == 'B' :
                        continue
                if now_color == 'G' :
                    if g[nh][nw] == 'B' :
                        continue

                d_blind.append((nh, nw))
                v_blind[nh][nw] = True

print(zone_nor, zone_blind)