백준 13549 - 숨바꼭질 3

백준

황태건 2023. 7. 19. 13:26

13549번: 숨바꼭질 3

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때

www.acmicpc.net

원리는 간단하다. 수빈의 위치에서 동생의 위치까지 BFS를 수행하면서 이동시간(cost)을 갱신한다. 이동시간의 갱신은 다음 두 경우에 이루어진다.

1) 다음 위치에 처음 접근할 때, 즉 cost[next]가 디폴트값(-1)일 때

2) 다음 위치에 이전에 접근한 적이 있지만, 현재 위치에서 이동할 경우 더 짧은 시간이 소요될 때.

즉 cost[cur] + 이동시간 < cost[next]

이동시간의 갱신은 1,2번 케이스 모두에서 이뤄지며, BFS를 위한 push는 1번 케이스에서만 진행된다. (아래 코드 참고)

if (cost[next] < 0)
    Q.push(next);
if (cost[next] < 0 || cost[next] > cost[cur] + 1)
    cost[next] = cost[cur] + 1;

케이스만 잘 따져도 문제를 쉽게 해결할 수 있다. 정작 나는 왜이렇게 시간을 오래 썼는지 모르겠다.

* 문제를 푸는 중에는 몰랐는데 2번 케이스는 dijkstra 알고리즘을 활용했다고도 볼 수 있겠다.