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

🎉 문제

 

 

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

 

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

 

 

🎉 풀이

✅ dfs 2번 사용하면 쉽게 풀리는 문제

     ✅ 적록색약인 경우와 아닌 경우로 나누어 탐색 진행

 

✅ 파이썬으로 재귀 함수 이용할 때 깊이 제한 안 풀어주면 런타임 에러 나므로 주의..

 

 

 

🎉 코드

import sys
sys.setrecursionlimit(10**6) #재귀함수 깊이 제한 늘려주기

#적록색약이 아닌 경우 DFS
def dfs(visited1, ground, i, j, n): 
  visited1[i][j] = True # 방문처리

  #상우하좌 순서 탐색
  di = [-1, 0, 1, 0]
  dj = [0, 1, 0, -1]

  for k in range(4):
    ni = i+di[k]
    nj = j+dj[k]

    if 0 <= ni < n and 0 <= nj < n: #GROUND 범위 내를 탐색하는데
      if not visited1[ni][nj] and ground[ni][nj] == ground[i][j]: #지금 기준이 되는 색깔과 탐색중인 색깔이 같으면
        dfs(visited1, ground, ni, nj, n) #다음으로 넘어가서 다시 탐색

#적록색약인 경우 DFS
def dfs2(visited2, ground, i, j, n):
  visited2[i][j] = True

  di = [-1, 0, 1, 0]
  dj = [0, 1, 0, -1]

  for k in range(4):
    ni = i+di[k]
    nj = j+dj[k]

    if 0 <= ni < n and 0 <= nj < n:
      if not visited2[ni][nj]:
        if ground[i][j] == 'G' or ground[i][j] == 'R': #지금 기준이 되는 색깔이 초록/빨강일 때는
          if ground[ni][nj] == 'G' or ground[ni][nj] == 'R': #다음 기준이 되는 색깔이 초록/빨강이면
            dfs2(visited2, ground, ni, nj, n) #또 탐색하러 갈 수 있음
            
            
        else: #지금 기준이 되는 색깔이 초록/빨강이 아니면
          if ground[ni][nj] == ground[i][j]: #기준이 되는 색깔이랑 다음 색깔이 똑같은 경우에만
            dfs2(visited2, ground, ni, nj, n) #탐색 진행할 수 있음
  


n = int(input()) # 입력값 n

ground = [list(input()) for _ in range(n)] #색깔 입력 받기

visited1 = [[False]*n for _ in range(n)] #적록색약 아닌 사람이 사용하는 방문체크
visited2 = [[False]*n for _ in range(n)] #적록색약인 사람이 사용하는 방문체크

normal_ground = 0 #적록색약이 아닌 경우 구분한 구역 개수
special_ground = 0 #적록색약인 경우 구분한 구역 개수

for i in range(n):
  for j in range(n): #그래프 돌면서 탐색
  	# 적록색약이 아닌 경우
    if not visited1[i][j]: # 이전에 체크하지 않은 색깔이면
      dfs(visited1, ground, i, j, n) # 주위에 이어진 같은 색깔 전부 탐색
      normal_ground += 1 #dfs 빠져나오면 구역 하나 탐색 끝난 것이므로 구역 개수 +1
    
    # 적록색약인 경우
    if not visited2[i][j]:
      dfs2(visited2, ground, i, j, n)
      special_ground += 1      

print(f'{normal_ground} {special_ground}')