다익스트라

이 문제는 한 마을에서 다른 마을로 이동할 때 비용(시간)이 주어질 때 다른 마을까지의 비용이 주어진 K보다 작은 마을의 개수를 구하는 문제이다. 가장 먼저 다익스트라가 떠올랐고 실제로 다익스트라 알고리즘을 통해 문제를 풀었다. 한가지 특이점은 보통 다익스트라는 목적지까지의 최소비용을 구할 때 많이 사용해온 알고리즘이지만 이 문제는 특별한 목적지가 존재하지 않다. 그렇기 때문에 나는 이 문제에서 heap 자료구조를 사용하지 않았다. 최소비용으로 갈 수 있는 경우에만 enqueue를 하면서 그래프 탐색을 하다가 더 이상 최소비용으로 갈 수 있는 도시가 없을 때 종료하도록 코드를 만들었다. (지금 생각해보니 heap을 사용하여 현재까지 비용이 K가 넘어가면 중지하는 식으로 구현해도 될 것 같다.) 정리하자면..

이 문제를 요약하자면 출발점에서 목적지까지 최단거리를 제외한 그다음 최단거리를 이용한다면 소요되는 비용을 묻는 문제이다. 이 문제를 풀기위한 나의 아이디어는 다익스트라로 우선 최단거리를 구한 후 그 결과를 활용하여 최단거리를 추적하고, 그 최단거리를 삭제한 후에 다시 다익스트라를 이용하여 최단거리를 구하는 것이다. 이를 정리하자면 아래와 같다. 1. 다익스트라를 통해 최단거리를 갈 때 비용을 기록 2. BFS를 활용해서 최단 루트 추적 -> 다익스트라를 기록한 배열을 활용하여 추적함 3. 다익스트라를 다시 하여 최소 비용 구하기 문제를 풀면서 생각한 엣지케이스는 최단거리가 여러 개일 수도 있다는 점이었기 때문에 최단거리를 추적할 때 이를 고려하여 최단 루트를 추적하였다. 이를 코드로 나타내면 아래와같다...

이 문제는 무지와 어피치가 출발점 S에서 택시를 타고 가는데 둘이 각자의 집으로 갈 때 최소 택시요금을 구하는 문제이다. 여기서 둘이 공통된 방향으로 택시를 타고 갈 때는 합승이 가능하다는 추가 조건이 있다. 이 부분까지 읽었을 때 다행이 내 머릿속에 바로 다익스트라가 떠올랐다. 다익스트라 알고리즘이란 그래프 경로 간에 가중치가 있는 경우, 한 꼭짓점에서 다른 꼭짓점 간의 최단 경로를 찾는 알고리즘이다. 나는 이 문제를 보고, 각 목표점(꼭짓점)과 그 사이를 이동할 때 택시요금(가중치)의 최단 택시요금을 구하는 점에서 다익스트라로 충분히 구현 가능하다고 생각했다. 하지만 이 문제를 풀기 위해서 추가로 고민했던 점이 있다. 1. 이 문제는 효율성 테스트도 점수가 있다. 시간/공간 제약을 정확히 명시해주지는..