[C++] 백준 1197 최소 스패닝 트리 / 최소신장트리

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main()
{
	int V = 0;	//정점의 개수
	int E = 0;	//간선의 개수
	int result = 0;	//총 가중치
	cin >> V;
	cin >> E;

	vector<vector<int>> lists;	//간선들 저장
	vector<int> visited(V + 1, false);	//방문했는지 1~V
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;	//가중치, 다음노드

	//입력
	for (int i = 0; i < E; i++)
	{
		vector<int> temp(3);

		for (int j = 0; j < 3; j++)
			cin >> temp[j];

		lists.push_back(temp);

		//1~V까지므로 1부터 시작점을 정함
		if (temp[0] == 1)
		{
			visited[1] = true;
			pq.push({ temp[2], temp[1] });
		}
		else if (temp[1] == 1)
		{
			visited[1] = true;
			pq.push({ temp[2], temp[0] });
		}

	}

	while (!pq.empty())
	{
		int currWeight = pq.top().first;
		int currNode = pq.top().second;

		pq.pop();

		if (visited[currNode] == false)
		{
			visited[currNode] = true;
			result += currWeight;

			for (int i = 0; i < E; i++)
			{
				int nextStart = lists[i][0];
				int nextEnd = lists[i][1];
				int nextWeight = lists[i][2];
				
                		//갈 수 있는 간선일 때
				if (nextStart == currNode && visited[nextEnd] == false)
					pq.push({ nextWeight, nextEnd });
				else if (nextEnd == currNode && visited[nextStart] == false)
					pq.push({ nextWeight, nextStart });
			}
		}
	}

	cout << result;

	return 0;
}

풀이

1. 방향이 없지만 한 방향으로만 그래프가 주어지므로 이것을 활용한다.

2. 1부터 시작하기 위해 start - end, end - start일 수도 있으므로 둘 다 확인을 하여 다음 정점을 넣어준다.

3. 우선순위 큐를 활용하여 가중치가 낮은 순으로 순회한다.

4. 방문한 곳을 방문하지 않는다.

5. 다음 정점에 도착했다면 현재 정점이 된다.

6. 현재 정점 도착하였다면 도착한 곳이지 않을 때만 가중치와 방문표시를 해준다.

7. 현재 정점에서 다음 정점으로 가는 간선들을 확인하는데 다음 정점이 방문하지 않은 곳만 추가해준다.

 

- 최소신장트리를 이용하여 푸는 문제인데 그 중 프림알고리즘을 채택하였습니다.

프림알고리즘 정보 : https://yabmoons.tistory.com/362

[ 프림 알고리즘 ] 개념과 구현방법 (C++)

 

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

1197번: 최소 스패닝 트리

비슷한 문제

https://programmers.co.kr/learn/courses/30/lessons/42861#

코딩테스트 연습 - 섬 연결하기