자바(백준) 16398 행성 연결

오답 노트 & 새로 알게 된 점

기본 MST 문제이다. 

다만 입력 부분에서 두 노드와 가중치를 주는 것이 아닌, 행렬로 주었다.

 

또한, 가중치가 최대 1억, N이 1000이므로 결과값이 Long이 나올 수 있다.

 

입력 부분에서 양방향이기 때문에 대각선을 기준으로 대칭이다.

----   

1   |  2 

    |

    ------

1번이나 2번 구역 중 하나의 구역만 선택하여 기본 MST처럼 풀면 된다.

 

---

코드

 

package bfs_dfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class BOJ16398 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N;
    static int parent[];
    static ArrayList<Info> al = new ArrayList<>();
    static long ans;

    public static void main(String[] args) throws IOException {
        input();
        pro();
    }

    static void pro() {
        Collections.sort(al, (o1, o2)->{
           return o1.wei - o2.wei;
        });

        int cnt = 0;

        for (int i = 0; i < al.size(); i++) {
            Info info = al.get(i);

            if (find(info.st) != find(info.ed)) {
                union(info.st, info.ed);
                ans += info.wei;
                if(++cnt == N - 1) break;
            }
        }

        System.out.println(ans);
    }

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = atoi(br.readLine());

        parent = new int[N + 1];
        Arrays.fill(parent, -1);

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int k = 0; k < i; k++) st.nextToken();
            for (int j = i; j < N; j++) {
                int wei = atoi(st.nextToken());
                al.add(new Info(i, j, wei));
            }
        }
    }

    static int find(int v) {
        if(parent[v] < 0) return v;
        parent[v] = find(parent[v]);

        return parent[v];
    }

    static void union(int u, int v) {
        u = find(u);
        v = find(v);

        if(u == v) return;
        parent[u] = v;
    }

    static class Info{
        int st, ed, wei;

        public Info(int st, int ed, int wei) {
            this.st = st;
            this.ed = ed;
            this.wei = wei;
        }
    }
}