[CodingTest] BOJ1697 숨바꼭질 ( BFS ) With 파이썬

 

 

1697번: 숨바꼭질

 

 

◎ 문제풀이 

 

N에서 K를 구하는 문제이다. 

 

연산은 3가지이다.  +1,  -1, x2

연산 한번에 1초가 소요되고 몇초가 걸리는지를 구하는 문제이므로, 연산횟수를 구하는 문제이다. 시작점과 목표점이 주어지고 최소연산횟수를 구하는 문제이다. 

 

1) DP가 아니라 BFS 문제

 

나는 DP가 먼저 연상되었다. 그러나 DP보다는 BFS가 더 적합한 알고리즘이다. 그 이유는 '시작위치'에 있다. DP는 더이상 쪼갤 수 없는 시작위치에서 목표지점까지 구하는 문제에 적용된다. 

 

DP를 활용한 타일링문제도 처음부터 끝까지 채우는 경우의수를 구하는 문제이다. 이런 연산자가 주어진 문제도 DP는 '1'로 만들어라 와 같이 더이상 쪼갤 수 없는 지점에서 시작되는 알고리즘이다. 반면, 위 문제는 다르다. 시작점은 1과 1000000 사이에 있는 어떤 수이다. 목표도 1과 1000000 사이에 있는 어떤 수이다. 원자적인 시작점에서 목표까지 하나씩 올라가는 문제가 아니라 아무위치에서 아무위치로 가는 경우를 탐색하는 문제이다. 

 

이런 경우는 BFS 알고리즘이 적합하다. 

BFS는 넓이우선탐색으로 형제를 먼저 탐색한다. 같은 연산횟수를 가진 형제를 먼저 탐색한다.

 

 

 

 

 

5에서 17을 탐색하는 경우를 보자. 최소연산횟수를 구하는 문제이므로 같은 연산횟수를 공유하는 형제노드를 먼저 탐색해야 한다. 형제를 먼저 탐색할 수 있도록 '큐' 자료구조를 사용한다. 

 

 

형제가 먼저 큐에 삽입되므로 먼저 탐색할 수 있다. 

 

2) 메모리제이션 

 

그럼 연산횟수를 어떻게 구할까?

 

자식의 연산횟수는 부모의 연산횟수의 +1이다. 그러므로 연산횟수 테이블을 하나 만든다. 부모는 자식을 큐에 PUSH하기 전에 자식의 연산횟수 테이블에 부모 연산횟수 + 1로 초기화한다. 이는 메모리제이션 기능도 한다. 만약 테이블이 초기화되어 있다면 이미 탐색되었다는 의미이므로 부모는 해당 자식을 큐에 PUSH 하지 않는다. 

 

 

◎ 코드

from collections import deque

MAX = 1000000
n,k = map(int,input().split())
d = [0] * (MAX+1)

#BFS 함수
def bfs(start,target) :
  q = deque()
  q.append(start) # 첫 루트노트 PUSH

  while q :
    value = q.popleft() 
    if value == target : break
    else :
      for next in (value+1,value-1,value*2) : # 부모가 자식을 큐에 PUSH하기
        if 0 <= next <= MAX and not d[next] : # 유효값이 아니거나 방문된 노드이면 제외
          d[next] = d[value] + 1 # 연산횟수 테이블 초기화
          q.append(next) # 큐에 PUSH
      
  return d[value]
      

print(bfs(n,k))