[BOJ] 백준 13549 숨바꼭질 3 (Swift)

문제

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

13549번: 숨바꼭질 3

풀이

이 문제는 간선의 비용이 0 또는 1이기 때문에 0-1 BFS를 사용하여 풀이할 수 있습니다.
또는 다익스트라 알고리즘을 사용해도 무방합니다.

0-1 BFS로 풀이를 할 때, 간선의 비용이 0인것 부터 처리해주기 때문에 queue보다는 deque 자료구조가 더 어울립니다.
insert 메서드로 큐에 앞부분에 삽입시켜주었는데 이는 시간복잡도가 $O(n)$이기 때문에 조금 느리지만 통과할 수 있었습니다.

다익스트라 알고리즘으로도 풀이를 해보았는데, insert 메서드를 사용한 것 보다는 빨랐습니다.

insert 메서드를 사용하지 않고, deque을 구현해서 풀이를 해보았는데 가장 빨랐습니다.

deque을 직접 구현하지 않고도, 간선의 비용이 0인 것들을 무조건 우선적으로 처리하는 방법으로도 구현이 가능할 것 같습니다.

소스코드

후기

여러가지 방법으로 풀이를 해보았는데, Deque으로 구현한 0-1 BFS가 가장 빨랐습니다.
알아보니 0-1 BFS의 시간복잡도가 다익스트라보다 더 효율적인 것을 확인했습니다.