[백준] [최단경로] [다익스트라] 13549. 숨바꼭질 3

13549. 숨바꼭질

13549번: 숨바꼭질 3

 

• 내 풀이 : 오답
  • 순간이동을 해야 거리가 0 추가 이기 때문에 최소값이 될수있음
  • → 무조건 *2 의 순간이동부터 해야함
  • +,- 부터 해버리면 에러
• 근데 dx=[2, -1, 1] 순으로만 정답 가능 , [2, 1, -1] 은 불가능
• → bfs로 푸는게 제대로된 풀이는 아닐 것 같다 !

from collections import deque

n,k=map(int,input().split())
dx=[1,-1,2]
queue=deque()
distance=[-1 for _ in range(100001)]

def bfs(start):
    global k
    queue.append(start)
    distance[start]=0
  
    while queue:
        q=queue.popleft()
        if q==k:
            print(distance[q])
            break
          
        for i in range(3):
            if i<2:
                d=q+dx[i]
                if 0<=d<=100000 and distance[d]==-1:
                    distance[d]=distance[q]+1
                    queue.append(d)
            else:
                d=q*dx[i]
                if 0<=d<=100000 and distance[d]==-1:
                    distance[d]=distance[q]
                    queue.append(d)

bfs(n)

 

• 다익스트라 풀이
  • 각 상황에 0, 1, 1의 거리값을 가지기 때문에 간선이 가중치를 가진다고 볼 수 있음 -> 다익스트라
  • [lambda x: 연산식] 으로 배열에 넣어놨기 때문에
  • move[i](now) : 배열에 인덱스값으로 불러온 식에 괄호(x) 를 붙여 값을 넣어준다

https://www.daleseo.com/python-yield/

import heapq

n,k=map(int,input().split())
queue=[]
INF=int(1e9)
distance=[INF for _ in range(100001)]
move=[lambda x:x+1, lambda x:x-1, lambda x:2*x]


def dijkstra(start):
    distance[start]=0
    heapq.heappush(queue,(0, start))
  
    while True:
        dist, now=heapq.heappop(queue)
    
        if dist>distance[now]:
            continue
        
        if now==k:
            print(dist)
            break
    
        for i in range(3):
            next=move[i](now)
            if next<0 or next>100000:
                continue
    
            if i==2:
              #새로운 거리가 더 짧을 경우에만 힙에 삽입
                if distance[next]> dist:
                    distance[next]=dist
                    heapq.heappush(queue,(distance[next],next))  
            else:
                if distance[next]> dist+1:
                    distance[next]=dist+1
                    heapq.heappush(queue,(distance[next],next))
      
dijkstra(n)