BOJ 16398 : 행성 연결

풀이 요약

MST (최소 신장 트리) 문제

풀이 상세

크루스칼 알고리즘

1. 크루스칼은 간선을 기반으로 한다. 따라서 입력값을 바꿔줄 필요가 있다. $i→ j$, $j→i$ 중복이 되므로, 정확히 입력값에서 $idx == idx$ 까지 제외한 반절 부분만 필요하다.

2. $(i<j)$ 경우에만 vector 에 담아주면 된다.

3. 유니온 파인드를 활용하여, 서로소 집합을 구한다. 서로소 집합이 동일한 경우라면 대표값이 기준점이거나 이미 한번 거친 노드이기에 넘어가고 아니라면 대표값을 바꿔준뒤 설치비용에 반영해주자.

4. 노드 $N$ 개를 모두 연결하기 까지 총 필요한 간선은 $N-1$ 이므로, $cnt == N-1$ 인 경우까지 탐색하고 반복문을 빠져나오자. (어차피 $cnt == N-1$ 이라면, 노드가 연결되어 대표값들이 모두 동일하기 때문에, 더이상 진행되지 않기는 한다.)

5. 출력하면 된다.

프림 알고리즘

1. 입력값을 통해 정점 리스트를 만든다.

2. 우선순위 큐를 통해 탐색이 진행된다. 현재 경우의 수 가운데 가장 작은 거리 값만 찾아 노드들을 연결하는 것이다. 사이클이 일어날 수 있는 경우를 대비하여, 방문처리를 해주자.

3. 임의의 노드에서, 다음 노드로 진행하는 경우, 만약 아직 방문한 적이 없는 노드라면 해당 노드로 진행이 될 수 있는 인덱스의 모든 경우의 수를 우선순위 큐에 담으며 탐색하자.

4. 출력하면 된다.

배운점

• 문제를 끝까지 봐야한다. long 조심하자.
• c++ 에서 배열 크기를 MAX 로 하여 이차원 배열을 생성하면 메모리 초과가 나온다. 이걸 N 으로만 해서, 함수의 인자로 잘 보내서 하면 될 거 같은데, 방법을 몰라서 c++ 로 결국 프림을 못만들었다. c++ 이랑 좀 더 친해지려면 메모리 할당이나 포인터에 대해서 공부를 해야 할 거 같다ㅠ

Kruskal

#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>
using namespace std;
typedef tuple<int, int, int> tp;
const int MAX = 1e4 + 3;
int p[MAX], N;
vector<tp> v;
bool cmp(tp &v1, tp &v2) { return get<2>(v1) < get<2>(v2); }
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        p[i] = i;
    }

    int arr[N + 1][N + 1];
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> arr[i][j];
            if (i < j)
                v.push_back(make_tuple(i, j, arr[i][j]));
        }
    }
    sort(v.begin(), v.end(), cmp);
}

int findSet(int n) {
    if (p[n] == n)
        return n;
    return p[n] = findSet(p[n]);
}

int unionParent(int e1, int e2) {
    e1 = findSet(e1);
    e2 = findSet(e2);
    if (e1 == e2)
        return 0;
    p[findSet(e2)] = findSet(e1);
    return 1;
}

long long kruskal() {
    long long ans = 0;
    int cnt = 0;
    for (int i = 0; i < v.size(); i++) {
        if (unionParent(get<0>(v[i]), get<1>(v[i]))) {
            ans += get<2>(v[i]);
            if (++cnt == N - 1)
                break;
        }
    }
    return ans;
}

void output() { cout << kruskal(); }

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    output();
    return 0;
}

Prim

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static class Edge implements Comparable<Edge>{
        int st, ed, dist;

        Edge(int st, int ed, int dist) {
            this.st = st;
            this.ed = ed;
            this.dist = dist;
        }

        @Override
        public int compareTo(Edge o) {
            return this.dist - o.dist;
        }
    }
    static List<Edge> list[];
    static boolean visited[];
    static PriorityQueue<Edge> pq = new PriorityQueue<>();
    private static void input() throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        list = new ArrayList[N];
        for(int i=0; i<N; i++) {
            list[i] = new ArrayList<>();
        }
        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++) {
                int dist = Integer.parseInt(st.nextToken());
                if(i==j) continue;
                list[i].add(new Edge(i,j,dist));
            }
        }
        visited = new boolean[N];
        pq.addAll(list[0]);
        visited[0] = true;
    }
    private static long prim() {
        int cnt = 1;
        long ans = 0;
        while(cnt < N) {
            Edge curr = pq.poll();
            if(visited[curr.ed]) continue;

            ans += curr.dist;
            pq.addAll(list[curr.ed]);
            visited[curr.ed] = true;
            cnt++;
        }
        return ans;
    }

    private static void output() {
        System.out.println(prim());
    }
    public static void main(String[] args) throws Exception{
        input();
        output();
    }
}