[백준] 13549번 숨바꼭질3(python)

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

13549번: 숨바꼭질 3

 

1. 난이도 골드5 (🥇)

 

2. 문제 해결 방법

다익스트라를 이용해서 순간이동과 걸어서 갈 때의 가중치를 다르게 두었다.

 

내가 놓쳤던 부분은

 

1. 수빈이가 동생보다 뒤에 있을 수 있다는 점

2. max 값이 100000 까지라는 점이다. => 최댓값을 동생의 위치 * 2로 했다가 틀렸다.

 

0-1 bfs 기 때문에 deque를 이용해서 풀 수 있다고 하는데 아직 그건 잘 모르겠다. 얘도 담에 복습하러 오겠슴,, 

 

3. 내가 작성한 코드

import heapq

INF = int(1e9)

n,k = map(int, input().split()) #n수빈 k동생

def dij(start):
  
  distance[start] = 0
  q = []
  heapq.heappush(q,(0,start))

  while q:
    dist, cur = heapq.heappop(q)

    if cur == k: #수빈과 동생의 위치가 같아지면 return
      return(dist)
    
    if distance[cur] < dist:
      continue
    
    for i in ((1,cur-1),(1,cur+1),(0,cur*2)):

      if i[1] > 100000 or i[1] < 0: #이동 범위를 벗어나면 continue
        continue

      cost = dist + i[0]

      if distance[i[1]] > cost: #최솟값으로 갱신
        distance[i[1]] = cost
        heapq.heappush(q,(cost,i[1]))

distance = [INF] * (100001)

print(dij(n))