백준#1185 유럽 여행 (Java)

전체코드

/**
 * author : MoonDooo
 * 백준 #1185 유럽여행
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args){
        new sol();
    }

}
class sol{
    Buf buf = new Buf();
    int N, P;
    public sol(){
        // 초기화
        N = buf.getInt();
        P = buf.getInt();
        int[] root = new int[N];
        int[] localCost = new int[N];
        PriorityQueue<Route> q = new PriorityQueue<>(Comparator.comparingInt(Route::getWeight));
        for (int i  =0 ;i<N; i++){
            root[i] = i;
        }

        //최솟값과 함께 도착 후 비용 저장
        int min = Integer.MAX_VALUE;
        for (int i = 0;i <N; i++){
            localCost[i] = buf.getInt();
            min = Math.min(min, localCost[i]);
        }

        //경로 비용 저장 (출발지 비용+도착지 비용+(2*교통비))
        for (int i = 0;i<P;i++){
            int s = buf.getInt()-1;
            int e = buf.getInt()-1;
            int weight = 2*buf.getInt()+localCost[s]+localCost[e];
            q.add(new Route(s, e, weight));
        }

        //MST 시작
        int[] height = new int[N]; //높이 측정을 위한 변수 ( 사실상 의미 없었다. )
        Arrays.fill(height,1);
        int tmp = 0;
        int result = 0;
        while (tmp!=N-1){
            Route poll = q.poll();
            if (union(root, height, poll.s, poll.e)){
                result += poll.getWeight();
                tmp++;
            }
        }

        System.out.println(result+min);
    }

    public int find(int[] root, int idx){
        if (root[idx] != idx) {
            root[idx] = find(root, root[idx]);
        }
        return root[idx];
    }

    public boolean union(int[] root, int[] height, int a, int b){
        int rootA = find(root, a);
        int rootB = find(root, b);
        if (rootA == rootB)return false;
        if (height[rootA]<=height[rootB]){
            root[rootA] = root[rootB];
            if (height[rootA]==height[rootB])height[rootB]++;

        }else{
            root[rootB] = root[rootA];
        }
        return true;
    }
}

class Route{
    int s;
    int e;
    int weight;
    public Route(int s, int e, int weight) {
        this.s = s;
        this.e = e;
        this.weight = weight;
    }


    public int getS() {
        return s;
    }

    public int getE() {
        return e;
    }

    public int getWeight() {
        return weight;
    }
}
class Buf{
    BufferedReader br;
    StringTokenizer st;
    Buf() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }
    public String get(){
        while(st==null||!st.hasMoreElements()){
            try{
                st= new StringTokenizer(br.readLine());
            }catch(IOException e){
                return null;
            }
        }
        return st.nextToken();
    }
    public Integer getInt(){
        return Integer.parseInt(get());
    }
}

풀이

문제는 최소 비용 경로를 탐색하는 것으로 보인다. 하지만 경로를 탐색하지 않고 쉽게 최소 비용만 구할 수 있다. 도시 N개에 대해 도로 N-1개만 사용하기 때문에 어떤 형태로든 모든 길은 2번 사용하게 된다.

왜냐하면 길이 N-1개이므로 사이클이 존재할 수 없기 때문이다. 즉 A->B, B->A에 드는 비용의 합을 가중치를 둔 MST 문제이다. 이때 교통비는 2번 들기 때문에 가중치 식은 (2*교통비) + A비용 + B비용이다. 주의할 점은 마지막 도착할 때 또한 비용으로 도착할 때의 비용이 가장 비용이 낮은 지역 비용만 따로 구해서 더해주면 된다.

코드

int min = Integer.MAX_VALUE;
for (int i = 0;i <N; i++){
    localCost[i] = buf.getInt();
    min = Math.min(min, localCost[i]);
}

도착지 비용을 구할 때 최솟값을 미리 저장해둔다.

//경로 비용 저장 (출발지 비용+도착지 비용+(2*교통비))
        for (int i = 0;i<P;i++){
            int s = buf.getInt()-1;
            int e = buf.getInt()-1;
            int weight = 2*buf.getInt()+localCost[s]+localCost[e];
            q.add(new Route(s, e, weight));
        }

풀이의 식 그대로 가중치를 넣어준다.

//MST 시작  
int[] height = new int[N]; //높이 측정을 위한 변수 ( 사실상 의미 없었다. )  
Arrays.fill(height,1);  
int tmp = 0;  
int result = 0;  
while (tmp!=N-1){  
Route poll = q.poll();  
if (union(root, height, poll.s, poll.e)){  
result += poll.getWeight();  
tmp++;  
}  
}

height는 낮은 트리를 높은 트리에 붙이기 위해서 사용했다. 하지만 이 문제에서는 크게 의미 없는 듯 하다. 사실상 무방향이므로 크루스칼을 이용했다.

public int find(int[] root, int idx){  
if (root[idx] != idx) {  
root[idx] = find(root, root[idx]);  
}  
return root[idx];  
}

public boolean union(int[] root, int[] height, int a, int b){
    int rootA = find(root, a);
    int rootB = find(root, b);
    if (rootA == rootB)return false;
    if (height[rootA]<=height[rootB]){
        root[rootA] = root[rootB];
        if (height[rootA]==height[rootB])height[rootB]++;

    }else{
        root[rootB] = root[rootA];
    }
    return true;
}

평범한 유니온 파인드이다. find는 부모를 찾아가며 반환할 때에는 경로 압축을 시켜주었다. union은 경로의 시작과 끝을 find를 사용하여 루트 노드를 찾고 서로 루트 노드가 다르다면 연결되지 않았다고 판단하고 높이가 낮은쪽에서 높은쪽에 붙는다. 이때 높이가 같을때만 상승한다.