BOJ 16398 : 행성 연결

·2023년 2월 10일
0

알고리즘 문제 풀이

목록 보기
57/165
post-thumbnail

풀이 요약

MST (최소 신장 트리) 문제

풀이 상세

크루스칼 알고리즘

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

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

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

  4. 노드 NN 개를 모두 연결하기 까지 총 필요한 간선은 N1N-1 이므로, cnt==N1cnt == N-1 인 경우까지 탐색하고 반복문을 빠져나오자. (어차피 cnt==N1cnt == 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();
    }
}
profile
새로운 것에 관심이 많고, 프로젝트 설계 및 최적화를 좋아합니다.

0개의 댓글