[프로그래머스/C++] 섬 연결하기

 

 

문제

문제 설명

 

 

[문제 요약]

​

섬과 섬을 연결하는 다리를 건설해 모든 섬을 이을 때, 최소 비용을 구하는 문제다. 이전에 풀었던 최소 신장 트리 문제와 똑같은 문제다. 

[SWEA/Python] 5249 - 최소 신장 트리

 

 

 

풀이

 

[풀이 요약]

 

섬위 범위가 100이기 때문에, 프림 알고리즘이나 크루스칼 알고리즘에서 사용하는 유니온, 우선순위 큐 등을 사용하지 않고 반복으로도 쉽게 풀릴 것이라 생각했다.

 

[아이디어 정리]

 

1. 첫번째 노드에서 방문할 수 있는 섬을 탐색하고 그 중에서 비용이 최소인 섬을 고른다.
2. 현재 방문한 섬들 중에서 현재 방문하지 않은 섬이면서 다음으로 방문했을 때 비용이 최소인 섬을 고른다.
3. 위 과정을 반복해 모든 섬을 방문하면 비용을 return 하면 된다.

 

 

Code

 

 

#include <string>
#include <vector>
using namespace std;

int realCost[100][100]={0,};
bool visit[100];
int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    int minCost=0, toVisitNode=0;
    for (int i=0; i<n; i++)
    {
        visit[i]=false;
    }
    visit[0]=true;    
    for (int i=0; i<costs.size(); i++)
    {
        realCost[costs[i][0]][costs[i][1]]=costs[i][2];
        realCost[costs[i][1]][costs[i][0]]=costs[i][2];
    }
    for (int cnt=1; cnt<n; cnt++)
    {
        minCost=10000000;
        for (int i=0; i<n; i++)
        { //시작노드가 0 이므로 빼도 된다.
            if (visit[i])
            {
                for (int k=1; k<n; k++)
                {
                    if (!visit[k]&&realCost[i][k]!=0)
                    {
                        if (minCost>realCost[i][k])
                        {
                            minCost=realCost[i][k];
                            toVisitNode=k;
                        }
                    }
                }
            }
        }
        visit[toVisitNode]=true;
        answer+=minCost;
    }
    return answer;
}

 

---

 

시간이 나면 union으로 시간을 줄이는 방법으로도 다시 풀어봐야지

 

프로그래머스