백준 13549번 숨바꼭질3 풀이/코드 (파이썬) 우선순위 큐를 활용한 bfs문제!

코드만 궁금한 분은 깃허브링크 눌러주세요!

GitHub - Rhyankwon/algorithms

문제 설명

 

숨바꼭질2 문제와 많이 비슷하다. 숨바꼭질2 문제와 다른점은 이번엔 2*x의 위치로 가는 경우에는 시간추가가 되지 않고, 그리고 움직이는 경우에 따라 움직이는 횟수와 관계없이 시간에 차이가 생기게되면서 이번엔 최소의 시간..값을 찾는 프로그램을 만들어야 한다.

문제 해결 논리

1. 현재의 위치에서 +1, -1, *2만큼 한 경우 이동하는 위치와 그 때마다 지나는 시간을 큐에 저장한다.
2. 큐에서 시간이 가장 작은걸 꺼내서 다시 1번을 반복한다.
3. 우리가 원하는 도착지점  K값이 나오면 그 때의 시간값을 반환하고 프로그램을 종료한다.

시간값이 작은 순서대로 값을 꺼내서 계산하고 있기 때문에 K값에 도달한 첫번째 시간값은 답에서 요구하는 최소의 시간을 만족한다.
이렇게 하면 곱셈부터 먼저 계산을 하는 형태라서, 만약 +1, +1, +1, *2, -1, *2, *2, *2 이런식으로 해야만 하는 경우, 특히 사소하게 +1이나 -1이 앞쪽에 많이들어가있어야 답이 나오는 경우까지 답이 도달하려면 그 이전에 불필요한 계산이 많이 들어가게된다. 하지만 어쩔 수 없는 부분이고 값이 10만범위라 충분히 문제에서 원하는 바를 만족하는 해설이다.

 

 

다른 풀이에 보면 굳이 시간값을 먼저 꺼내지 않는 형식으로도 풀리게 한 코드가 많던데 그게 논리적으로 맞는건지..는 잘 모르겠다. 내가 놓치고 있는 부분이 있나 싶은데 아직 잘 모르겠다. 누가 좀 알려주세요 ,,ㅋㅋㅋ