[백준] 10026번 적록색약 파이썬 풀이 -DFS, BFS

문제 설명

링크

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

문제

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

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

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

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

 

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

 

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

 

예제입력/출력

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

4 3

 

문제 풀이

아이디어

1. 색이 다른 블록이 나올 때까지 dfs로 탐색한다. => 탐색이 끝나면 카운트 1 증가.

2. 이미 방문한 블록을 체크할 수 있도록 0으로 초기화한 2차원 배열 check를 만든다.

3. 적록색약이 아닌 경우를 먼저 구해준다. 이중 반복문을 돌면서 check가 0인 곳을 dfs 함수를 돌린다. 이때 인자로 좌표값과 색상을 넣어준다.

4. 위의 과정이 끝나면 check가 전부 1로 초기화 되어 있다. 적록색약인 경우 check가 1인 곳을 방문하지 않은 곳으로 보고, 방문했을 때 0으로 바꿔준다.

5. 적록색약인 경우에 조건 하나를 추가해준다. 블록의 색상이 R또는 G인 경우, "RG"를 dfs의 color 파라미터로 넘겨준다. dfs에 색상을 비교해줄 때 "비교할 색상" in "RG" 형태로 하기 때문에 R또는 G를 같은 것으로 판단한다.

 

 

 

풀이

import sys

sys.setrecursionlimit(10**6) #재귀호출 제한을 늘림

input= sys.stdin.readline

n= int(input())

palette=[]

for _ in range(n):

  palette.append(list(input().strip()))

check=[[0]*n for _ in range(n)]

d= [(0,-1),(0,1),(1,0),(-1,0)]

#dfs 제사용을 위해 방문 여부를 visited로 체크한다.

visited= 1

def dfs(c,r,color):

  global check

  if check[c][r] == visited: #방문여부 확인

    return

  check[c][r]=visited #방문 체크

  for dc, dr in d: #4방향 dfs탐색

    new_c = c+ dc

    new_r= r+dr

    if(new_c<0 or new_c>=n or new_r<0 or new_r>=n):#범위가 같지않다면 스킵

      continue

    if(palette[new_c][new_r] not in color): #색상이 같지않다면 스킵

      continue

    dfs(new_c,new_r,color)

 

result1=0 #적록색약 아닌 경우

result2=0 #적록색약인 경우

#적록색약 x의 경우

for i in range(n):

  for j in range(n):

    if(check[i][j]!=visited):

      dfs(i,j,palette[i][j])

      result1+=1

#적록색약인 경우, 방문한 곳을 0으로 본다.

visited=0

#적록색약인 경우

for i in range(n):

  for j in range(n):

    if(check[i][j]!=visited):

      if palette[i][j]=="R" or palette[i][j]=="G":

        dfs(i,j,"RG")

      else:

        dfs(i,j,"B")

      result2+=1

print(result1, result2)