[프로그래머스/알고리즘] 섬 연결하기

문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

입출력 예

n : 4

costs : [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]

return : 4

해결 방법

costs에서 나와 있는 것을 이용해서 행렬을 만들었습니다.

그리고 가장 짧은 것을 구합니다.

입출력 예에서 가장 짧은 것은 0, 1번째 섬의 다리 길이는 1입니다. 

그리고 0, 1은 방문했기 때문에 이를 확인하기 위한 visit 배열을 통해 방문 표시를 합니다. 그리고 길이를 결과값에 더해줍니다.

그다음 0,1이 연결 되어 있는 것중에서 가장 짧은 값을 구합니다. 1번 째 섬과 연결되어 있는 3번째 섬이 가장 짧기 때문에 3번째 섬도 방문 표시를 하고 결과값에 길이를 더 합니다.

그 다음 0, 1 ,3이 연결 되어 있는 것중에서 가장 짧은 값을 구합니다. 0번째 섬과 연결되어 있는 2번째 섬이 가장 짧이 때문에 2번째 섬에 방문 표시를 하고 결과값을 길이에 더 합니다.

이러한 방식으로 계속 반복해서 전체의 섬이 다 방문할 때까지 반복하면 값이 나옵니다.

소스 코드

#include <string>
#include <vector>
using namespace std;
bool checkVisit(vector<bool> visit);

int solution(int n, vector<vector<int>> costs) {
	int answer = 0;
	vector<bool> visit(n);
	vector<vector<int>> temp(n,vector<int>(n));
	int min = costs[0][2];
	int minnode1=costs[0][0], minnode2=costs[0][1];
	for (int i = 0; i < costs.size(); i++) {		//그래프화
		temp[costs[i][0]][costs[i][1]] = costs[i][2];
		temp[costs[i][1]][costs[i][0]] = costs[i][2];
		if (costs[i][2] < min) {
			min = costs[i][2];
			minnode1 = costs[i][0];
			minnode2 = costs[i][1];
		}
	}
	answer += min;
	visit[minnode1] = true;
	visit[minnode2] = true;
	min = -1;
	
	while (checkVisit(visit)) {
		for (int i = 0; i < visit.size(); i++) {
			if (visit[i] != true)
				continue;
			for (int j = 0; j < visit.size(); j++) {
				if ((min == -1 || min > temp[i][j]) && visit[j] != true && temp[i][j] != 0) {
					min = temp[i][j];
					minnode1 = i;
					minnode2 = j;
				}
			}
		}
		visit[minnode1] = true;
		visit[minnode2] = true;
		answer += min;
		min = -1;
	}
	return answer;
}

bool checkVisit(vector<bool> visit) {
	for (int i = 0; i < visit.size(); i++) {
		if (visit[i] == false) {
			return true;
		}
	}
	return false;
}