[그리디, 난이도 중] 프로그래머즈, 섬 연결하기

최소 비용으로 모든 노드를 연결할 때에 사용되는 대표적인 알고리즘 2개가 있다.

1. 크루스칼 알고리즘

먼저, 모든 간선들을 오름차 순으로 정렬 한다.

비용이 적은 간선부터 그 간선으로 인한 사이클의 발생 여부를 판단하여 사이클이 생기지 않는다면, 그 간선을 채택하는 알고리즘이다.

자세한 설명과 예시는 위키피디아를 참고하면 좋을 것이다.

ko.wikipedia.org/wiki/%ED%81%AC%EB%9F%AC%EC%8A%A4%EC%BB%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

크러스컬 알고리즘 - 위키백과, 우리 모두의 백과사전

2. 프림 알고리즘

연결이 이미 이루어진 모든 노드들의 모든 간선들중 가장 적은 비용의 간선을 채택하는 알고리즘이다.

맨 먼저 시작점 노드를 골라야 하는데 아무 노드나 골라도 결과가 같다는 특징이 있다.

프림 알고리즘 역시 위키피디아 링크를 걸어두겠다.

ko.wikipedia.org/wiki/%ED%94%84%EB%A6%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

프림 알고리즘 - 위키백과, 우리 모두의 백과사전

 

본인이 개인적으로 마음에 들어하는 프림 알고리즘을 썼다.

프림 알고리즘에서 새로 연결된 노드가 생길때마다, 그 노드의 간선을 priority_queue에 모두 push해주면 최적의 시간복잡도로 가장 적은 비용의 간선을 채택할 수 있게 된다. 

자세한 설명은 모두 코드 주석에 달아놓을 것이다.

 

테스트 케이스 8개 모두 통과

 

#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct node {
	int cost; //비용
	int des; //인접 노드
};

priority_queue<node> pq;
vector<node> a[101]; //인접 노드 정보들을 모아둔 벡터
bool visited[101]; //노드 방문 여부

bool operator<(node a, node b) {
	return a.cost > b.cost;
}

int solution(int n, vector<vector<int>> costs) {
	int answer = 0;
	int visit_count = 1; //방문한 노드의 수
	int node = 0; //프림 알고리즘 시작점 노드를 0으로 설정
	int _des, _cost; //노드 요소 임시 저장 변수
	visited[node] = true;
	for (int i = 0; i < costs.size(); i++) { //인접 노드 추가
		a[costs[i][0]].push_back({ costs[i][2],costs[i][1] });
		a[costs[i][1]].push_back({ costs[i][2],costs[i][0] });
	}

	while (visit_count != n) { //모든 노드가 연결 될 때 까지 반복문 수행
    	//이미 연결되어 있는 노드의 간선들은 신경 쓸 필요가 없다.
		for (int i = 0; i < a[node].size(); i++) {
			if (!visited[a[node][i].des]) pq.push(a[node][i]);
		}
		while (1) {
        	//pq.top() : pq에 있는 노드들중 cost가 최소인 노드
			_des = pq.top().des;
			_cost = pq.top().cost;
			if (visited[_des]) pq.pop(); //그 간선이 사이클을 만들 경우 무시
			else break; //간선 채택 완료
		}
		answer += _cost; //비용 추가
		node = _des; //새로 연결된 노드
		visited[_des] = true; //노드 방문 체크
		visit_count++; //연결된 노드 카운트 증가
	}
	return answer;
}