[Python] 백준 #1697- 숨바꼭질[try_again]

문제

---

1697번: 숨바꼭질

코드

---

Another answer

import sys 
from collections import deque 
input = sys.stdin.readline() 

def bfs(): 
    q = deque() 
    q.append(n) 
    while q: 
        x = q.popleft() 
        if x == k: 
            print(dist[x]) 
            break 
        for j in (x-1,x+1,x*2): 
            if 0<= j <= MAX and not dist[j]: 
                dist[j] = dist[x] +1 
                q.append(j) 
                
MAX = 100000 
n,k = map(int,input.split()) 
dist = [0] * (MAX+1) 
bfs()

풀이

---

우선 나는 이 문제를 못풀었다. 재귀방식으로 해보려고했는데, 재귀는 너무 어려운 것 같다. 다른 분의 코드를 가져왔다.

우선 코드에서 dist는 깊이를 의미한다. 즉 이 문제에서는 초를 의미한다. 이 문제는 너비우선탐색으로 푸는 문제다. 너비우선탐색에 대해서는 알고리즘 카테고리에 작성하도록 하겠다. 우선 5로 시작을하면 for문을 4,6,10 순으로 돌아가는데,바로 전 깊이 즉 초에다가 1을 늘려주는 계산을 하고, 계속 저장을 해준다. 다음으로는 맨 마지막에 들어간 10부터 같은 과정을 반복해준다. 10이들어가면 9,11,20이 for문을 돌게되고 또 저장되고 반복하다보면 나오게 된다.