[백준][파이썬] 10026번. 적록색약

문제

https://www.acmicpc.net/problem/10026

 

풀이

구역의 개수를 구하는 알고리즘은 적록색약 여부와 무관하게 dfs로 구현할 수 있다.

import sys
sys.setrecursionlimit(10**6)

N = int(input())
picture = []
for _ in range(N) :
  picture.append(list(input()))

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

def dfs(x, y, c) :  # c : 색깔(R, G, B)
  visited[x][y] = 1  # 방문처리

  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] == 0 :  # 방문하지 않았고
      if picture[nx][ny] == c :  # 현재 색깔과 동일하면
        dfs(nx, ny, c)
        
# 색약이 아닌 사람
visited = [[0 for _ in range(N)] for _ in range(N)]
sum1 = 0

for c in ['R', 'G', 'B'] :
  for i in range(N) :
    for j in range(N) :
      if visited[i][j] == 0 and picture[i][j] == c :
        dfs(i, j, c)
        sum1 += 1
        
# 적록색약인 사람
for i in range(N) :
  for j in range(N) :
    if picture[i][j] == 'R' :  # 적록색약인 사람은 R과 G를 구별하지 못하므로 미리 R을 G로 바꾼다
      picture[i][j] = 'G'
visited = [[0 for _ in range(N)] for _ in range(N)]
sum2 = 0

for c in ['G', 'B'] :
  for i in range(N) :
    for j in range(N) :
      if visited[i][j] == 0 and picture[i][j] == c :
        dfs(i, j, c)
        sum2 += 1
        
print(sum1, sum2)