· 최초 아이디어
일반적인 다익스트라 구현 문제에서 그 경로를 구하는 작업만 추가된 문제이다. 경로를 저장하기 위해 간단하게 string 자료형을 선택하였다.
우선순위 큐에 방문할 노드 정보를 저장할 때 여태까지 어떤 노드를 방문해왔는지 정보를 포함하여 구조체로 선언하였다. 이때, 갑자기 문제가 발생했다.
검색해보아도 해결법이 보이지 않아, 코드를 한 줄 한 줄 지워가며 원인을 찾았고, 위와 같이 우선순위 큐의 push() 함수를 호출할 때 문제가 발생하였다. 결론적으로 커스텀 구조체를 우선순위 큐에 저장할 때 어떤 필드로 우선순위를 결정할지 기준을 잡아주지 않은 탓이었다.
· 커스텀 구조체로 priority_queue 사용하기
struct Info {
int distance;
int nodeNum;
std::string path;
bool operator < (const Info& info) const {
return distance > info.distance;
}
};따라서 이와 같이 커스텀 구조체 안에 구조체의 대소 비교를 위한 연산자 오버로딩을 통해 우선순위를 지정해주었다. CPP의 pair STL은 대소 비교 연산자 오버로딩이 돼있어 따로 설정해주지 않았었던 것을 간과하고 있었다.
priority_queue STL은 기본적으로 Max heap이기 때문에 작은 값을 힙의 최상단으로 옮기기 위해서 커스텀 구조체의 대소 비교 기호와 실제 반환되는 대소 관계를 반대로 설정해주어 Min heap으로 작동하도록 만들었다.
잘 작동하는 것을 확인하고 제출하였지만, 실패하였다. 그 이유는 여러가지가 있다.
-
같은 경로에 다른 가중치를 가지는 버스가 2개 이상 주어지는 경우
예를 들어, 1번 노드에서 3번 노드로 가는 경로가 2개 이상 주어질 수 있다.
1 3 5와1 3 7이 동시에 주어졌을 때 최소를 저장하도록 설정해주어야 한다. 이 부분은 항상 처리해주기 때문에 필자의 코드에선 문제가 되지 않았다. -
출발점과 도착점이 같을 때
예를 들어 1번에서 출발하여 1번으로 도착하는 경우가 있다고 하자. 다음과 같은 입력이 주어진다./**** input ****/ 1 1 1 1 0 1 1이때 올바른 출력은 다음과 같다.
/**** output ****/ 0 1 1그 경로의 비용은 0이고, 거치는 도시는
1하나이다. 이것이 가능하도록 자기 자신에 대한distance를 0으로 초기화해주었다. -
도시가 두 자릿수 이상인 경우
경로를string으로 저장하려고 해 발생한 문제이다. 한 자릿수인 경우엔 경로 문자열의 문자 인덱스를 하나씩만 옮기면 되지만, 도시 번호가 두 자리 이상이 넘어가면 인덱스를 하나씩 옮기면 안 된다. 따라서 도시 번호를 저장할 때마다' '문자를 추가하여 구분해주었다. -
도시가 두자릿수인 경우 string의 길이가 안 맞아서 tokenization 필요
위 문제와 함께 발생한 또다른 문제이다. 경로를 출력하면서 거친 도시 수를 출력해야 했는데, 경로 문자열의length()를 출력하려고 했을 때 두 자릿수 이상의 도시와 도시 사이를 구분하기 위한' '문자도 길이에 포함되는 것이 문제가 되었다. 따라서 문자열을 공백에 따라 Tokenization해주는vector컨테이너를 새로 만들어주었다.
처음엔 간단하게 구현하기 위해 string을 활용했던 것인데, 오히려 점점 복잡해지고 있는 것을 느꼈지만, 결과는 잘 나오는 것 같아 그대로 제출해보았다. 틀렸다.
· 경로 저장 방식 변경
string 자료형으로 경로를 저장하는 것이 문제였던 것 같다. vector 컨테이너를 만들어 그 경로를 저장하고자 했다. 다음 노드를 방문하는 더 효율적인 경로를 발견하면 현재 노드의 경로 정보를 복사하고 다음 노드를 경로에 추가해주었다.
if (path[adj.second].first > curDistance + adj.first) {
path[adj.second].first = curDistance + adj.first;
path[adj.second].second.assign(path[curNodeNum].second.begin(), path[curNodeNum].second.end());
path[adj.second].second.push_back(adj.second);
}... 경로 벡터를 옮기는 과정이 복잡해 맘에 들지 않지만 그래도 시도해본다. 틀렸다.
· 최최최종 아이디어
많은 시행착오를 겪었지만, 근본적인 아이디어 문제가 있다고 판단했다. 다른 이들의 코드를 참고한 결과, 특정 노드를 방문하는 최소 비용을 저장하면서, 이 비용을 가지기 위해 '어떤 노드에서 왔는지'를 저장하였다.
이 정보를 이용하면 도착 노드에서부터 출발 노드까지 최소 비용을 가지게 만든 경로를 역추적할 수 있다.
해당 아이디어를 저장한 최종 코드는 아래와 같다.
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#define MAX_SIZE 1001
#define INF 2000000001
int n, m;
int startNode, endNode;
std::priority_queue<std::pair<int, int>> q;
std::vector<std::pair<long long, int>> graph[MAX_SIZE];
std::pair<long long, int> path[MAX_SIZE];
void dijkstra(int startNode) {
path[startNode].first = 0;
for (auto adj : graph[startNode]) {
q.push({ -adj.first, adj.second });
if (path[adj.second].first > adj.first) {
path[adj.second] = { adj.first, startNode };
}
}
while (!q.empty()) {
long long curDistance = -q.top().first;
int curNodeNum = q.top().second;
q.pop();
if (path[curNodeNum].first >= curDistance) {
for (auto adj : graph[curNodeNum]) {
if (path[adj.second].first > curDistance + adj.first) {
path[adj.second] = { curDistance + adj.first, curNodeNum };
q.push({ -path[adj.second].first, adj.second });
}
}
}
}
}
void init() {
for (int index = 1; index <= n; index++) {
path[index] = { INF, 0 };
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
std::cin >> n >> m;
int node1, node2, weight;
for (int count = 0; count < m; count++) {
std::cin >> node1 >> node2 >> weight;
graph[node1].push_back({ weight, node2 });
}
std::cin >> startNode >> endNode;
init();
dijkstra(startNode);
std::vector<int> route;
for (int trace = endNode; trace != 0; trace = path[trace].second) {
route.push_back(trace);
}
std::cout << path[endNode].first << "\n" << route.size() << "\n";
for (int index = route.size() - 1; index >= 0; index--) {
std::cout << route[index] << " ";
}
}