[프로그래머스 Level3] 섬 연결하기 (C++)

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

프로그래머스

문제 설명

---

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

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

 

제한사항

---

섬의 개수 n은 1 이상 100 이하입니다.
costs의 길이는 ((n-1) * n) / 2이하입니다.
임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
연결할 수 없는 섬은 주어지지 않습니다.

 

입출력 예

---

n	costs	return
4	[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]	4

 

문제 풀이

---

MST 문제.

우선순위 큐를 이용해 비용이 작은 다리부터 하나씩 연결 가능한지 확인한다.

union-find 알고리즘을 이용해 연결을 했을 때 싸이클을 형성한다면 연결하지 않고, 형성하지 않는다면 해당 다리를 연결한다.

 

아래는 코드.

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
int* parents;

struct info
{
    int A;
    int B;
    int cost;
    info(int a, int b, int c)
    {
        A=a;
        B=b;
        cost=c;
    }
};

int find(int x)
{
    if (parents[x] == x)
    {
        return x;
    }
    else
    {
        return parents[x] = find(parents[x]);
    }
}

void merge(int x, int y)
{
    int parentX=find(x);
    int parentY=find(y);
    if (parentX < parentY)
    {
        parents[parentY]=parentX;
    }
    else
    {
        parents[parentX]=parentY;
    }
}

struct cmp
{
  bool operator()(info& i1, info& i2)
  {
      if (i1.cost < i2.cost)
      {
          return false;
      }
      else
      {
          return true;
      }
  }
};

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    parents=new int[n];
    priority_queue<info, vector<info>, cmp> pq;
    for (int i=0;i<n;i++)
    {
        parents[i]=i;
    }
    for (int i=0;i<costs.size();i++)
    {
        int a=costs.at(i).at(0);
        int b=costs.at(i).at(1);
        int c=costs.at(i).at(2);
        pq.push(info(a, b, c));
    }
    while (!pq.empty())
    {
        info current=pq.top();
        int parentX=find(current.A);
        int parentY=find(current.B);
        if (parentX != parentY)
        {
            merge(current.A, current.B);
            answer+=current.cost;
        }
        pq.pop();
    }
    return answer;
}