알고리즘(C++) / 프로그래머스 level 3 : 섬 연결하기

level 3 : 섬 연결하기

https://programmers.co.kr/learn/courses/30/lessons/42861?language=cpp# 

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

코드

//프로그래머스 섬 연결하기
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
bool visited[101] = { false, };

bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[2] < b[2];
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;

    sort(costs.begin(), costs.end(), cmp);

    //가장 작은 간선 선택
    visited[costs[0][0]] = true;
    visited[costs[0][1]] = true;
    answer += costs[0][2];

    int count = 2; //연결된 노드 두개

    while (1) {
        for (int i = 1; i < costs.size(); i++) {
            if (visited[costs[i][0]] ^ visited[costs[i][1]]) {
                //연결된 노드
                visited[costs[i][0]] = true;
                visited[costs[i][1]] = true;
                answer += costs[i][2];
                count++;
                break;
            }
        }
        if (count == n) {
            break;
        }
    }

    return answer;
}

int main() {
    int n = 5;
    vector<vector<int>> costs = { {0,1,1}, {0,2,2}, {1,2,1},{1,3,3}, {2,3,8},{3,4,1} };
    cout << solution(n, costs) << "\n";
    return 0;
}

 

설명

MST(Minimum Spanning Tree, 최소 신장 트리)

: spanning tree 주에서 사용된 간선들의 가중치 합이 최소인 트리.(spanning tree는 그래프의 최소 연결 부분 그래프)

MST를 찾는 알고리즘은 Kruskal Algorithm(크루스칼 알고리즘), Prim Algorithm(프림 알고리즘) 두가지가 있다. 

이 알고리즘은 다음번에 더 자세히 설명하도록 하겠다. 

 

다음 알고리즘을 알고 구현하진 않았지만 내 방식은 Prim Algorithm을 사용하였다. 

 

1. costs 벡터를 간선의 오름차순에 따라 정렬한다.

2. 가장 작은 간선을 선택한다. 

3. visted 배열은 노드가 연결되었는지 안되었는지를 판단한다. 

4. 모든 노드가 연결될 때까지 while문을 반복한다. 

5. 이때 노드가 연결되는 조건은 ^(xor)으로 구분한다. 노드 두개로 이루어진 간선 중에서 노드 두개 중 하나만 visited에서 true일 때 연결이 가능하다.  

6. 모든 노드가 연결되었으면 while문을 종료한다. 

 

 

 

고찰

크루스칼과 프림 알고리즘을 알지 못하고 여러 테스트 케이스를 실행하보면서 문제를 풀었다.

후에 다른 사람들의 풀이를 봤을때 MST 알고리즘을 사용해서 푸는 것을 알게 되었다. 이 알고리즘을 알고는 있었지만 배운지 좀 되서 바로 기억이 나지 않았다. 알고리즘 한번더 정리하면서 공부해야될거 같다.