[문제해결기법] 길동이의 여행

정답 코드

이 문제는 최소 스패닝 트리로 푸는 문제이다.

최소 스패닝 트리를 간단히 설명하자면

1. 최소 거리를 순서대로 저장해 놓는다

2. 만약 그 거리를 연결했을 때 사이클이 돈다면 설정하지 않는다

3. 사이클이 돌지 않는다면 연결시키고 결과 값에 더해준다.

#include <iostream> #include <vector> #include <queue> #include <fstream> #include <functional> using namespace std; #define PAIR pair<int,pair<int,int>> vector<int> parent; int find(int index) { if (index == parent[index]) return index; else return parent[index] = find(parent[index]); } int Union(int start, int end) { start = find(start); end = find(end); if (start == end) return 0; parent[start] = end; return 1; } int main() { int for_count, node_count, edge_count, start, end, time; cin >> for_count; while (for_count--) { cin >> node_count >> edge_count; parent.clear(); parent = vector<int>(node_count); priority_queue<PAIR, vector<PAIR>, greater<PAIR>> node; for (int j = 0; j < node_count; j++) parent[j] = j; for (int j = 0; j < edge_count; j++) { cin >> start >> end >> time; node.push(make_pair(time, make_pair(start, end))); } long long result = 0; while (!node.empty()) { time = node.top().first; start = node.top().second.first; end = node.top().second.second; node.pop(); if (Union(start, end)) result += time; } cout << result << endl; } }

이건 오답코드이다.

위와 다른 점은 parent를 초기화하는 시간을 줄이기 위해 꼼수를 썼다는 것이다.

아래와 같으면 왜 되지 않을까

parent의 최대 값은 N이다 그리고 간선의 최소 값은 N-1이다 

나는 N값을 모두 초기화 시켜야하는데 간선의 개수가 N-1이기때문에 마지막이 초기화가 되지 않는다.

따라서 이 코드가 계속해서 오류가 났다.

#include <iostream> #include <vector> #include <queue> #include <fstream> #include <functional> using namespace std; #define PAIR pair<int,pair<int,int>> vector<int> parent; int find(int index) { if (index == parent[index]) return index; else return parent[index] = find(parent[index]); } int Union(int start, int end) { start = find(start); end = find(end); if (start == end) return 0; parent[start] = end; return 1; } int main() { int for_count, node_count, edge_count, start, end, time; cin >> for_count; while (for_count--) { cin >> node_count >> edge_count; parent.clear(); parent = vector<int>(node_count); priority_queue<PAIR, vector<PAIR>, greater<PAIR>> node; for (int j = 0; j < edge_count; j++) { if(j<node_count) parent[j] = j; cin >> start >> end >> time; node.push(make_pair(time, make_pair(start, end))); } long long result = 0; while (!node.empty()) { time = node.top().first; start = node.top().second.first; end = node.top().second.second; node.pop(); if (Union(start, end)) result += time; } cout << result << endl; } }