[백준알고리즘] 1697번: 숨바꼭질 -Python

[백준알고리즘] 1697번: 숨바꼭질 -Python

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

1697번: 숨바꼭질

처음에 이번 문제를 DFS 방식으로 풀으려 했다. 백트래킹으로 여러 조건들을 추가해서 가지치기를 함으로써 시간을 줄이려 했다.

 

시간도 괜찮을 것 같았는데 input으로 "0 100000"만 주더라도 계산을 못해버리는 것을 보고는 더 추가할 조건이 없었기 때문에 코드를 지웠다..

 

DFS 방식은 최소 길이, 최소 거리와 같은 최소 경로를 구하는 데 있어서는 비효율적이다. 오히려 BFS는 이러한 최소 길이를 구하는 데 있어서 더 효율적이라고 볼 수 있다. 이번에는 백트래킹 방식으로도 통과가 가능할 줄 알았는데 시간 초과가 발생했었다....

DFS로 생각되는 문제들은 풀기 전에 BFS 방식으로도 해결이 가능한지 먼저 생각을 해봐야겠다.

 

import sys
from collections import deque
 
def solve():
    while position:
        p, s = position.popleft()
 
        if p == k:
            return s
        
        s += 1
        if 0 < p < k and p*2 < bound and not visited[p*2]:
            visited[p*2] = 1
            position.append((p*2, s))
        if p < k and p+1 < bound and not visited[p+1]:
            visited[p+1] = 1
            position.append((p+1, s))
        if p-1 >= 0 and not visited[p-1]:
            visited[p-1] = 1
            position.append((p-1, s))
 
n, k = map(int, sys.stdin.readline().split())
bound = 100001
visited = [0]*bound
visited[n] = 1
position = deque([(n, 0)])
 
print(solve())

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다