[백준] 14950 정복자 ⛳️ (Java)

문제 링크

https://www.acmicpc.net/problem/14950

문제 설명

서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재한다. 각각 도시는 1번부터 N번까지 번호가 붙여져 있다. 그 중에서 1번 도시의 군주 박건은 모든 도시를 정복하고 싶어한다.

처음 점거하고 있는 도시는 1번 도시 뿐이다. 만약 특정 도시 B를 정복하고 싶다면, B와 도로로 연결된 도시들 중에서 적어도 하나를 정복하고 있어야 한다. 조건을 만족하는 도시 중에서 하나인 A를 선택하면, B를 정복하는 과정에서 A와 B를 연결하는 도로의 비용이 소모된다. 박건은 한번에 하나의 도시만 정복을 시도하고 언제나 성공한다. 한 번 도시가 정복되면, 모든 도시는 경계를 하게 되기 때문에 모든 도로의 비용이 t만큼 증가하게 된다. 한 번 정복한 도시는 다시 정복하지 않는다.

이때 박건이 모든 도시를 정복하는데 사용되는 최소 비용을 구하시오.

입력

첫째 줄에 도시의 개수 N과 도로의 개수 M과 한번 정복할 때마다 증가하는 도로의 비용 t가 주어진다. N은 10000보다 작거나 같은 자연수이고, M은 30000보다 작거나 같은 자연수이다. t는 10이하의 자연수이다.

M개의 줄에는 도로를 나타내는 세 자연수 A, B, C가 주어진다. A와 B사이에 비용이 C인 도로가 있다는 뜻이다. A와 B는 N이하의 서로 다른 자연수이다. C는 10000 이하의 자연수이다.

출력

모든 도시를 정복하는데 사용되는 최소 비용을 출력하시오.

구조화

최소 스패닝 트리?….허허

기억도 안나서 기본 최소 스패닝 트리에서 변형함

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static class Node implements Comparable<Node>{
        int from;
        int to;
        int wight;

        public Node(int from, int to, int wight) {
            this.from = from;
            this.to = to;
            this.wight = wight;
        }

        @Override
        public int compareTo(Node n){
            return this.wight - n.wight;
        }
    }

    public static int N, M, t;
    public static int[] parents;
    public static List<Node> list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());

        list = new LinkedList<>();
        parents = new int[N+1];


        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int wight = Integer.parseInt(st.nextToken());

            list.add(new Node(from, to, wight));
        }
        Collections.sort(list);
        set();

        int sum = 0;
        int cnt = 0;

        for (Node n : list) {
            if (union(n.from, n.to)){
                sum += n.wight+(cnt*t);
                cnt++;
                if (cnt == M-1) break;
            }
        }
        System.out.println(sum);
    }

    public static void set(){
        for (int i = 1; i <= N; i++) {
            parents[i] = i;
        }
    }

    public static boolean union(int from, int to){
        int fromRoot = find(from);
        int toRoot = find(to);
        if (fromRoot == toRoot) return false;
        else {
            parents[fromRoot] = toRoot;
        }

        return true;
    }

    public static int find(int v){
        if (parents[v] == v) return v;
        else return parents[v] = find(parents[v]);
    }
}

 

그 전에 실패한 코드...

import java.io.*;
import java.util.*;

public class Main {
    static class Node {
        int idx;
        int next;
        int val;

        public Node(int idx, int next, int val) {
            this.idx = idx;
            this.next = next;
            this.val = val;
        }
    }

    static final int start = 1;
    static int n, m, t, total = 0, ans = Integer.MAX_VALUE;
    static List<Node>[] list;
    static boolean[] v;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());

        v = new boolean[n+1];
        list = new List[n+1];
        for (int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int idx = Integer.parseInt(st.nextToken());
            int next = Integer.parseInt(st.nextToken());
            int val = Integer.parseInt(st.nextToken());

            list[idx].add(new Node(next, idx, val));
            list[next].add(new Node(idx, next, val));
        }

        /*for (int i = 1; i <= n; i++) {
            list[i].sort((o1, o2) -> o1.val - o2.val);
        }*/
        bfs1();
        System.out.println(ans);

        /*v[1] = true;
        dfs(new Node(1, 0, 0), 0, 0);
        System.out.println(ans);*/

    }

    static void bfs1() {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {start, 0, 0});
        v[start] = true;

        while (!q.isEmpty()) {
            int cur = q.peek()[0];
            int cnt = q.peek()[1];
            int val = q.peek()[2];
            q.poll();

            System.out.println(val);
            if (cnt >= n-1) {
                ans = Math.min(val, ans);
            }

            for (Node next : list[cur]) {
                if (v[next.idx]) continue;
                v[next.idx] = true;
                q.offer(new int[] {next.idx, cnt+1, val+next.val+(cnt*t)});
            }
        }
    }
    static void bfs() {
        int cnt = 0;
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        v[start] = true;

        while (!q.isEmpty()) {
            int cur = q.poll();
            cnt++;

            if (cnt >= n-1) {
                break;
            }

            for (Node next : list[cur]) {
                if (v[next.idx]) continue;
                q.offer(next.idx);
                total += next.val+(t*cnt);
                v[next.idx] = true;
            }
        }
    }

    static void dfs(Node cur, int cnt, int val) {
        if (cnt == n-1) {
            ans = Math.min(ans, val);
            return;
        }

        for (Node next : list[cur.idx]) {
            if (v[next.idx]) continue;
            v[next.idx] = true;
            dfs(next, cnt+1, val+(next.val+(cnt*t)));
            v[next.idx] = false;
        }
    }
}