문제 (https://www.acmicpc.net/problem/13549)
13549번: 숨바꼭질 3
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
작년에 BFS로 풀었던 1697 숨바꼭질과 비슷한 문제이다.
다익스트라 알고리즘 스터디 주간에 고른 문제여서 다익스트라로 해결해보려 했지만,, 문제를 읽고 생각을 해봐도 1697번 문제처럼 BFS로 해결하는 방법밖에 떠오르지 않았다...! 그래서 일단 BFS로 해결 완! (코드 첨부)
BFS로 해결할 경우 방문 순서에 따라 정답이 되기도 하고 아니기도 한다. 문제 질문 검색 카테고리의 글들을 읽어보다가 이 의문에 대한 해답을 알게 되었다...!! (출처)
- BFS는 모든 간선의 가중치가 동일해야 한다는 전제 조건이 필요
- 문제의 특성 때문에 방문 순서에 따라서 단순 BFS로도 우연히도 항상 정답을 찾을 수 있을 뿐
이렇게 간선의 가중치가 다를 경우에는 BFS 알고리즘으로 푸는 게 옳지 않다는 것을 알게 되었다........ 🙂
A에서 B로 갈 때 C의 가중치를 갖는다. => 이런 전형적인 다익스트라 입력이 아니어서 처음에 접근하기가 힘들었다.
생각을 해보면.. 더 단순하다! 우선순위 큐를 확인하면서 다음 위치까지 걸리는 시간이 갱신되면 다음 위치를 우선순위 큐에 넣어주면 된다. 이때 확인해줄 것은 순간이동의 경우와 걸어서 이동의 경우를 따로 계산해주어야 하는 것뿐이다.
[Dijkstra]
[BFS]
'ALGORITHM > BOJ' 카테고리의 다른 글
| [BOJ] 2096번 내려가기 (C++) (0) | 2022.01.19 |
|---|---|
| [BOJ] 2211번 네트워크 복구 (C++) (0) | 2022.01.17 |
| [BOJ] 1238번 파티 (C++) (0) | 2022.01.17 |
| [BOJ] 2887번 행성 터널 (C++) (0) | 2022.01.05 |
| [BOJ] 1939번 중량제한 (C++) (0) | 2022.01.05 |