BOJ - 정복자 14950번 (JAVA)

❓ 문제 - 백준 정복자14950번 - JAVA 풀이법

 

출처 

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

14950번: 정복자

 

 

 

📝 문제해결법

1. 이 문제는 MST(최소신장트리)로 풀이했다.

• 부모 찾기와 합집합을 구현하여 사이클이 생기지 않은 조건에서 최소신장트리를 만들어 모든 노드를 최소 비용으로 연결하도록 구현한다.
• 그러나 문제에서 최소신장트리를 구현하면서 최소 비용을 구할 때, 노드가 연결될 때마다 비용 t가 계속 추가적으로 증가한다는 것이다.
• 이것을 노드를 연결해줄 때마다 cnt를 통해 카운트 해주고 cnt를 이용해서 cost에 값을 반영해서 답을 출력하면 된다.

 

2. 느낀점

• MST 알고리즘 문제여서 바로 구현 과정의 생각 없이 코딩하면 다 되는 문제였는데
• 이건 MST 알고리즘이지만 이게 MST가 맞나? 라는 의심을 계속 하면서 구현했던 것 같다.
• 1번 도로부터 정복을 시작해서 모든 도로를 다 정복했을 때 드는 비용을 계산인데 시작점에서 다른 값을 구하니깐 다익스트라인가? 고민했다. 하지만  특정 노드에서 특정 다른 노드까지의 지나가는 비용 계산이 아닌 정복할 수 있는 마지막까지 다 찾고 그 때까지 걸린 비용을 계산하므로 최소신장트리 풀이가 맞는 것이다. 

 

 

💻 소스코드

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

public class Main_14950 {
    public static int[] parent;
    public static class Node implements Comparable<Node>{
        int nodeA;
        int nodeB;
        int distance;
        public Node(int nodeA, int nodeB, int distance){
            this.nodeA = nodeA;
            this.nodeB = nodeB;
            this.distance = distance;
        }

        @Override
        public int compareTo(Node o) {
            return this.distance - o.distance;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());
        ArrayList<Node> edges = new ArrayList<>();
        parent = new int[n];
        for(int i=0;i<n;i++){
            parent[i] = i;
        }
        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            edges.add(new Node(a-1, b-1, c));
        }

        Collections.sort(edges);
        int cnt = 0;
        int cost = 0;
        for(Node node:edges){
            if(find_parent(node.nodeA) != find_parent(node.nodeB)){
                cost += (cnt * t + node.distance);
                union(node.nodeA, node.nodeB);
                cnt++;
            }
        }

        System.out.println(cost);
    }

    public static int find_parent(int x){
        if(x == parent[x]) return x;
        return parent[x] = find_parent(parent[x]);
    }

    public static void union(int a, int b){
        a = find_parent(a);
        b = find_parent(b);
        if(a < b){
            parent[b] = a;
        } else {
            parent[a] = b;
        }
    }
}