[백준-골드5] 13549번 숨바꼭질 3(BFS, 파이썬)

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

13549번: 숨바꼭질 3

 

[주의할 점]

- 이 문제가 기존 숨바꼭질 문제와 다른 점은 순간이동을 하는 경우 0초 후에 2*X의 위치로 이동하는 것이다.

- BFS는 모든 간선의 가중치가 동일해야 한다는 전제조건이 있다.

- 따라서 이 문제는 가중치가 0인 간선(순간이동)이 존재하기 때문에 기존 BFS로는 풀수 없다.

  (정답 통과한 코드에서 이동 순서가 [2*x, x-1, x+1]일때 통과하긴 하지만 우연히 답 찾은 경우)

- 이 문제는 다익스트라 알고리즘 또는 0-1BFS를 이용해야한다. 난 다익스트라는 아직 몰라서 0-1 BFS를 이용했다.

- 0-1 BFS는 가중치가 0인 간선에 연결된 정점은 큐의 맨 뒤가 아닌 맨 앞에 넣는 방법이다. appendleft() 이용

 

<내 코드>

- dist의 크기는 문제에서 주어진 최대 길이로 정했다.

- 아직 방문하지 않은 곳을 순회한다. 이 때 nx가 2*x인 경우 dist[nx] = dist[x]로 이동시간 0초를 의미하고

  큐에 삽입할때 맨 앞에 넣어준다.

- 2*x가 아닌 경우에는 거리를 1 증가시키고 그냥 큐에 삽입한다.

- 목적지 k가 n보다 작거나 같은 경우는 n-k를 리턴하고

- 그렇지 않은 경우는 dist의 k번째 값을 리턴한다.

from collections import deque
import sys
input = sys.stdin.readline
n, k = map(int, input().split())

dist = [-1]*(100001)

def bfs(x):
    queue = deque()
    queue.append(x)
    dist[x] = 0
    while queue:
        x = queue.popleft()
        if x == k:
            return dist[k]
        for nx in [x+1,x-1, 2*x]:
            if 0<=nx<len(dist):
                if dist[nx] ==-1:
                    if nx !=2*x:
                        dist[nx] = dist[x]+1
                        queue.append(nx)
                    else: #이동 시간이 0 (즉 가중치 0)
                        dist[nx] = dist[x]
                        queue.appendleft(nx) #큐의 맨 앞에 삽입
                                    
if k<=n:
    print(n-k)
else:
    print(bfs(n))