[백준]1697번 숨바꼭질 파이썬 python

문제 링크

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

1697번: 숨바꼭질

 

코드

import sys
from collections import deque
input = sys.stdin.readline
 
n, k = map(int,input().split())
MAX = 200000
check = [-1]*(MAX+1)
dq = deque()
check[n]=0
dq.append(n)
 
while dq:
    x = dq.popleft()
    if x==k:
        break
    for nx in [x+1, x-1, 2*x]:
        if 0<=nx<=MAX and check[nx]==-1:
            check[nx]=check[x]+1
            dq.append(nx)
ans = check[k]
print(ans)
 

핵심Point

- 가중치가 1인 최단길이를 구할 때 BFS를 사용한다. (가중치 존재 시, 다익스트라 알고리즘 사용)

- MAX값을 고려해야하는데, 가능한 연산이 x+1, x-1, 2*x이므로 최대를 20,000으로 잡을 수 있다. (x<=10,000)

- BFS의 시간복잡도는 O(V정점갯수+E간선수)

이때, 최대 정점수가 10,000이고 최대 간선수는 30,000 (B/C. 각 정점에서 3가지 행동가능) --> 총 40,000내에 해결가능