BOJ 10026 적록색약

문제

접근 방법

간단한 bfs 문제였다.

풀이 코드

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

'''
모든 지점에서 bfs를 진행해서 구역 개수를 구한다.

적록색약에서는 빨강과 초록이 같다고 하고 구역 개수를 구한다.
'''

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

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

moves = [[1,0],[-1,0],[0,1],[0,-1]]

def bfs(start_y,start_x, base):
  q = deque()
  q.append([start_y,start_x])
  visited[start_y][start_x] = True
  while q:
    h,w = q.popleft()
    for dh, dw in moves:
      new_h, new_w = h+dh, w+dw
      if 0<=new_h<n and 0<=new_w<n and colors[new_h][new_w]==base and not visited[new_h][new_w]:
        visited[new_h][new_w] = True
        q.append([new_h, new_w])

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

def bfs_1(start_y,start_x, base):
  q = deque()
  q.append([start_y,start_x])
  visited_1[start_y][start_x] = True
  base_colors = set()
  if base == 'G' or base == 'R':
    base_colors.add('G')
    base_colors.add('R')
  else:
    base_colors.add('B')
  while q:
    h,w = q.popleft()
    for dh, dw in moves:
      new_h, new_w = h+dh, w+dw
      if 0<=new_h<n and 0<=new_w<n and colors[new_h][new_w] in base_colors and not visited_1[new_h][new_w]:
        visited_1[new_h][new_w] = True
        q.append([new_h, new_w])

areas = 0
areas_1 = 0

for i in range(n):
  for j in range(n):
    if not visited[i][j]:
      bfs(i,j,colors[i][j])
      areas+=1

for i in range(n):
  for j in range(n):
    if not visited_1[i][j]:
      bfs_1(i,j,colors[i][j])
      areas_1+=1

print(f"{areas} {areas_1}")