[Python] DFS/BFS - 10026. 적녹색약(골5) / 탐색 기준값이 변수

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

1. 문제

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

10026번: 적록색약

---

2. 핵심 아이디어

2-1) 적녹색약의 관점에서 세상보기

: 우선 이 문제를 처음 보자마자 탐색 문제라는 것은 인식하는 것에는 큰 어려움이 없었다.

중요한 문제, 즉 걸림돌은 어떻게 적록색약의 관점에서 진행하는 탐색을 구현할 것인가? 였다.

 

적록색약은 빨간색(R)과 초록색(G)의 차이를 느끼지 못한다.

즉, R과 G를 같은 하나의 색깔로 인지한다.

따라서 R과 G를 하나의 색깔로 통일한 이후 탐색을 진행해주면 되는 문제였다.

 

 

2-2) 탐색의 기준 파악하기

: 기존의 탐색문제는 탐색값이 1과 같이 정해져 있었다. 그러나, 이번 문제는 영역을 구하는 문제다.

따라서 탐색을 시작한 색깔과 같은 색깔끼리 탐색을 진행해야 한다.

 

즉, 빨간색에서 탐색을 진행했다면 빨간색일 경우에만 탐색을 진행하고

파란색에서 탐색을 진행했다면 파란색일 경우에만 탐색을 진행하고

초록색에서 탐색을 진행했다면 초록색일 경우에만 탐색을 진행해야 한다.

 

탐색의 기준이 특정값이 아닌, 변수라는 점에서 차이가 있었다.

---

3. 코드 구현

#10026 적녹색약- G와 R을 구분하지 못함

from collections import deque
import copy

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

def bfs(i,j, graph):

  color= graph[i][j]
  q= deque([(i,j)])
  graph[i][j]=0

  while(q):
    x,y= q.popleft()
    #상하좌우 탐색
    for k in range(4):
      nx= x+dx[k]
      ny = y+dy[k]

      #범위는 넘치지 않는가?
      if nx<0 or ny<0 or nx>=n or ny>=n:
        continue
      
      #만약 탐색을 시작한 색깔과 같은 색깔이면 같은 영역
      # 따라서 0으로 초기화하면서 큐에 넣어 탐색을 이어감
      if graph[nx][ny]==color:
        q.append((nx, ny))
        graph[nx][ny]=0



n= int(input())

graph=[]

for _ in range(n):
  graph.append(list(map(str, input())))

graph_cpy= copy.deepcopy(graph)

#일반 사람이 볼 경우
result=0
for i in range(n):
  for j in range(n):
    if graph[i][j]!=0:
      bfs(i,j, graph)
      result+=1

print(result, end=' ')

#적녹색약의 경우 G=>R로 바꾸어 통일

for i in range(n):
  for j in range(n):
    if graph_cpy[i][j]=='G':
      graph_cpy[i][j]='R'


#일반 사람이 볼 경우
result=0
for i in range(n):
  for j in range(n):
    if graph_cpy[i][j]!=0:
      bfs(i,j, graph_cpy)
      result+=1

print(result)

---

4. 배운 점

단순 값의 탐색이 아닌 기준값이 변수가 되는 탐색이라 흥미로웠다.

적록색약의 관점에서 한번더 탐색을 진행해야 하기에 copy.deepcopy를 통해

값이 같은 graph객체를 하나 더 만들어야 된다는 점을 유의하자.