18352 특정 거리의 도시 찾기

18352 특정 거리의 도시 찾기 / c++ / Silver2 / 30분

문제 및 코드

접근 방식

그래프 / 다익스트라

1. 각 도시간의 거리는 1이다.
2. 최대 도시 수는 300’000으로, 인접행렬로 구하기엔 공간 복잡도가 높다.
   -> 인접 리스트를 사용
3. 시작 도시 X에서 다익스트라 알고리즘으로 각 도시까지의 거리를 구한다.
4. 계산이 끝나면 그 중 거리가 K인 도시를 사전 순으로 출력, 없다면 -1을 출력한다.

다시 생각해 볼 점

1. 다익스트라 알고리즘을 적용해 볼 수 있는 비교적 간단한 문제였다.
2. 각 도시간의 거리가 1이라는 점, 큐와 다익스트라의 성질에 의해 먼저 접근한 도시가 당연히 거리가 짧게 된다. (그래서 거리를 비교할게 아니라 방문만 했다면 바로 건너뛰면 됨)
3. 1차 시도에서 시간이 960ms가 나와서 왜 그런지 찾아봤더니 인접 리스트를 저장할 때 Map으로 저장한게 시간을 지연시켰었다. 300’000개나 되는 도시를 다 저장하지 않아도 된다고 생각해서 검색 속도가 빠른 Map을 사용한 것이었는데, 이정도 규모에서는 그냥 Vector를 사용하는 것이 훨씬 효율이 좋았다. (심지어 메모리도 더 적게 차지했다.)
4. 간만에 자료구조에 대해 다시 생각해볼 수 있는 좋은 경험이었다.