SWEA 1251. [S/W 문제해결 응용] 4일차 - 하나로

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD

SW Expert Academy

 

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

class Tunnel {
    int v1, v2;
    long cost;
    Tunnel(int v1, int v2, long cost) {
        this.v1 = v1;
        this.v2 = v2;
        this.cost = cost;
    }
}

public class Main {
    static long answer;
    static int[] unf;
    static int[] x, y;
    static ArrayList<Tunnel> arr;
    public static int Find(int v) {
        if(v == unf[v]) return unf[v];
        else return unf[v] = Find(unf[v]);
    }
    public static void Union(int a, int b) {
        int fa = Find(a);
        int fb = Find(b);
        if(fa!=fb) unf[fa] = fb;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        for(int test_case = 1; test_case <= T; test_case++)
        {
            int n = Integer.parseInt(br.readLine());
            x = new int[n];
            y = new int[n];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i=0; i<n; i++) {
                x[i] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine());
            for(int i=0; i<n; i++) {
                y[i] = Integer.parseInt(st.nextToken());
            }
            double e = Double.parseDouble(br.readLine());
            answer = 0;
            unf = new int[n];
            for(int i=0; i<n; i++) unf[i] = i;
            arr = new ArrayList<>();
            for(int i=0; i<n; i++) {
                for(int j=i+1; j<n; j++) {
                    arr.add(new Tunnel(i,j,(long)(x[i]-x[j])*(x[i]-x[j]) + (long)(y[i]-y[j])*(y[i]-y[j])));
                }
            }
            Collections.sort(arr, (o1, o2) -> Long.compare(o1.cost, o2.cost));
            int cnt = 0;
            for(Tunnel ob : arr) {
                int fv1 = Find(ob.v1);
                int fv2 = Find(ob.v2);
                if(fv1!=fv2) {
                    answer += ob.cost;
                    Union(ob.v1, ob.v2);
                    cnt++;
                    if(cnt == n-1) break;
                }
            }
            sb.append("#").append(test_case).append(" ").append(Math.round(answer*e)).append("\n");
        }
        System.out.println(sb);
    }
}

 

최소스패닝트리(MST) 문제

필요한 개념 : Union & Find (크루스칼 알고리즘)

unf 배열 : 각 인덱스와 같은 숫자로 초기화. 각 인덱스는 섬의 번호를 의미하며 배열값은 속한 집합을 의미한다. 즉, "섬 0은 집합 0에 속해있다" 라는 뜻. 처음에는 당연히 모두 서로소.

Find 함수 : 재귀함수를 통해 입력으로 들어온 번호의 섬이 "최종으로" 속해 있는 집합 번호를 찾아준다.

Union 함수 : 두 섬의 번호를 입력으로 받아 Find 함수를 호출해서 각각 값을 받고 비교 후 다르면 unf[fa]= fb 를 통해 같은 Union, 즉 같은 집합 번호로 묶어준다.

 

더 자세히 설명해보자면, 

예를 들어 최소 비용 순으로 정렬된 arr에서 먼저 (0, 1, 최소비용)에 대해 연산을 시행한다.

섬 0과 섬 1의 각각의 Find 함수 입력 결과, 서로 다른 값이므로 같은 집합이 아니다. 따라서 Union 작업을 해줘야 한다.

Union 함수를 시행하면 unf[0] = 1, 섬 0은 집합 1이 된다. 이제 트리상에서 섬 0과 섬 1은 연결된 하나의 집합이 되었다.

 

섬	0	1	2	3	4	...
집합	1	1	2	3	4	...

 

이후 또다른 경우로, (0, 2, 최소비용)에 대해 연산을 시행하면 각각 집합 1과 집합 2에 속해있으므로 Union 작업을 해줘야 한다.

Find(0) = 1, Find(2) = 2 서로 다르므로 아래와 같이 unf[1] = 2 로 변경해준다.

(이 때 Find(0) = 1은 단순히 표를 보고 한게 아닌, Find(0) = Find(1) = 1 과정을 거친 것이다.)

 

섬	0	1	2	3	4	...
집합	1	2	2	3	4	...

 

결과적으로 섬 0의 집합번호가 배열에서 직접적으로 바뀌지 않아도 재귀를 통해 도달할 수 있는 최종 집합 번호인 unf[1]이 2로 바뀜으로서 Union이 되는 것이다.

또한 만약 (0, 3, 최소비용)에 대해서도 연산을 시행할 경우 Find(0)을 호출하게 되는데, 이때 Find(0) = Find(1) = Find(2) = 2 순으로 재귀호출을 하게 된다.

 

public static int Find(int v) {
    if(v == unf[v]) return unf[v];
    else return unf[v] = Find(unf[v]);
}

 

else 문에 의해 unf[0] = 2 로 변경되고 이제부터 추후에 Find(0)을 하게된다면 재귀 호출시 Find(1)을 건너띄고 바로 Find(2)를 호출하게 되는 경로 압축의 효과가 발생한다. 재귀를 덜 호출하게 되는 것이다.

 

지금까지 예시를 통해 섬의 집합 번호가 직접 바뀌는 경우, 간접적으로 바뀌는 경우를 확인해봤고,

어떠한 예시의 경우는 재귀를 덜 호출하게 하는 경로 압축의 효과가 발생하는 것도 확인했다.

위와 같은 Union & Find 작업을 통해 최소 비용으로 모두 연결된 섬의 트리가 완성된다.

 

그리고 순환이 존재하지 않는 트리, 최소스패닝트리(MST)이므로 간선의 개수는 노드의 개수 - 1이다. 따라서 Union 연산, 즉 간선을 이어주는 연산을 (노드의 개수 - 1) 번 만큼 하고나면 더이상 할 필요가 없으므로 cnt = 0 초기화 해주고 cnt = n-1이 됐을 때 다음 case로 넘어가도록 break를 해준다.