[백준][python]1697 숨바꼭질

문제

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

소스코드

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

if __name__ == "__main__":
    n,k = map(int,input().split())
    check = [-1] * 100001

    q = deque()
    q.append(n)
    check[n] = 0

    while q:
        cur = q.popleft()
        for i in (cur-1,cur+1,cur*2):
            if 0 <= i <= 100000 and check[i] == -1:
                check[i] = check[cur] + 1
                q.append(i)

    print(check[k])

설명

최단거리를 구하는 문제는 BFS가 유리하다. 왜냐하면 DFS의 경우 처음 발견되는 해답이 최소거리가 아닐 수 있지만,

BFS의 경우 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리이다.

 

처음에 DP + DFS 로 해서 recursion error 발생