[SWEA] 1251번 하나로 자바(java) 풀이( MST, 크루스칼 알고리즘)

sw expert academy 1251번 하나로 자바(java) 풀이

• 난이도 : D4
• sw expert academy 1251번 하나로
  
  
  

문제정리

1. 모든 섬들을 해저터널로 연결하려 한다.
2. 해저터널은 반드시 두 섬을 선분으로 연결하며, 두 해저 터널이 교차된다 하더라도 연결되지 않은 것으로 본다.
3. 환경부담금 : 환경 부담 세율(E) * 해저터널 길이(L)²

• 횐경 부담금을 최소로 지불하며, N개의 모든 섬을 연결할 수 있는 교통 시스템 설계해라!
  
  
  

문제풀이

Spanning Tree(스패닝 트리)는 그래프에서 모든 노드를 포함하면서 순환 경로가 없는 트리를 이야가 합니다.
그 중에서 가중치의 합을 최소로 하는 트리를 Minimal Spanning Tree(MST)라고 합니다.
즉, 이 문제는 MST를 만들면 풀 수 있는 문제입니다. 모든 섬을 연결하면서 섬을 잇는 가중치들의 합이 최소가 되어야 하기 때문입니다.
MST를 만드는 알고리즘에는 크게 2가지 알고리즘이 거론됩니다.

1. 크루스칼 알고리즘
2. 프림 알고리즘

이 문제에서는 크루스칼 알고리즘을 이용하도록 하겠습니다.

크루스칼 알고리즘 간단 설명

1. 모든 간선들의 가중치를 오름차순으로 정렬한다.

2. 가중치가 가장 작은 간선을 선택한다.

3. 선택한 간선이 연결되어있지 않은 상태이면 두 노드를 연결한다.

4. 위 과정을 반복한다.
   예를 들어 보겠습니다.
   그래프 정보를 n1 n2 weight 형태로 표현하였습니다.

   a b 1
   a c 12
   a d 3
   b c 4
   b d 10
   c d 2

5. 간선에 대한 가중치를 기준으로 정렬하겠습니다.

   a b 1
   c d 2
   a d 3
   b c 4
   b d 10
   a c 12

6. 가중치가 가장 작은 간선을 선택하고 연결하고 반복한다.
   a b를 선택하고 연결합니다.
   c d를 선택하고 연결합니다.
   a d를 선택하고 연결합니다.
   b c를 선택하였는데 b와 c는 b->a->d->c로 연결되어 있습니다.
   이하 마찬가지로 모두 연결되어 있습니다.

7. b->a->d->c로 연결하면 가중치의 합이 6으로 가장 작게 됩니다.
   
   
   

union-find

크루스칼 알고리즘에서 선택한 간선의 두 노드가 연결되어있는지 확인해야합니다.
이를 확인하기 위해서 union-find 방식을 많이 사용합니다.
말 뜻 그대로 찾고 합치는 것입니다.
Union
두 노드가 연결되어 있지 않으면 합칩니다.
이때 합침을 표현하기 위해서 parent[]라는 배열을 주로 사용합니다.
1번 정점의 부모는 parent[1]가 됩니다.
부모를 갖게 만들어줘서 두 노드가 연결되었음을 나타냅니다.
초기 값은 자기자신을 부모로 합니다. ex) parent[1]=1, parent[2]=2 ...
Find
이는 부모를 찾는다라는 뜻입니다.
서로 다른 두 정점의 부모를 찾아봤을 때, 같다면 연결하지 않고
서로 다르다면 연결할 수 있습니다.
부모가 다르더라도 이미 다른점을 통해 연결되었을 수 있기 때문에 이를 검사합니다.

findParent 함수

이 함수의 return에서 다음과 같이 해도 답은 구할 수 있습니다.

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

하지만 이렇게 하지 않고 다음과 같이 구현하였습니다.

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

이렇게 하면 부모를 찾는 시간을 많이 줄일 수 있습니다.
예를 들어 한쪽으로 편향된 트리가 만들어졌다면 맨 위 노드까지 올라가 부모를 찾기 위해서 최대 n번의 재귀를 호출해야 합니다.
하지만 중간 중간에 부모의 값을 갱신해주면 바로 위의 하나만 올라가도 부모를 알 수 있습니다.

i = 1 2 3 4 5 6 7 8 9
parent[i] = 1 1 2 3 4 5 6 7 8 과 같을때 9의 부모를 찾게 되면
총 8번의 재귀적 호출이 필요합니다.

하지만 밑에 함수로 하게 되면 parent의 값들이 1로 이미 되어있어서
재귀적 호출을 많이 할 필요가 없어지게 됩니다.
parent의 의미는 이어져있음이 중요한 것이 아니라
부모가 누구냐가 제일 중요하기 때문에 밑에 함수와 같이 작성합니다!!

두 함수의 시간을 비교해보면 위의 함수를 사용하면 3.701초가 걸렸고
아래의 함수를 사용했을 때는 2.056초로 꽤 많은 시간의 차이가 났습니다.

swea 1251번 하나로 자바 코드

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

class Pos {
    int x;
    int y;
    double weight;

    Pos(int x, int y, double weight){
        this.x = x;
        this.y = y;
        this.weight = weight;
    }
}

class Solution {
    static int n;
    static Pos[] island;
    static double E;    
    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testNum = Integer.parseInt(br.readLine());

        for(int test=1; test<=testNum; test++){
            n = Integer.parseInt(br.readLine());
            island = new Pos[n];

            String[] temp = br.readLine().split(" ");
            // x좌표
            for(int i=0; i<n; i++)
                island[i] = new Pos(Integer.parseInt(temp[i]), 0, 0);

            // y좌표
            temp = br.readLine().split(" ");
            for(int i=0; i<n; i++)
                island[i].y = Integer.parseInt(temp[i]);

            // 환경 부담 세율
            E = Double.parseDouble(br.readLine());
            ArrayList<Pos> weights = new ArrayList<>();

            // 모든 점들과 각각의 weight 구하기
            for(int i=0; i<n-1; i++){
                for(int j=i+1; j<n; j++){
                    weights.add(new Pos(i, j, calWeight(island[i].x, island[i].y, island[j].x, island[j].y)));
                }
            }

            // weight 기준으로 sort
            Collections.sort(weights, new Comparator<Pos>() {
                @Override
                public int compare(Pos p1, Pos p2){
                    if(p1.weight < p2.weight)
                        return -1;
                    else if(p1.weight > p2.weight)
                        return 1;
                    return 0;
                }
            });

            // 두 점의 연결 여부를 확인할 parent 배열
            parent = new int[n];
            for(int i=0; i<n; i++)
                parent[i] = i;

            double ans = 0.0;
            for(int i=0; i< weights.size(); i++){
                // 부모가 같지 않다면 연결되어있지 않음 => union
                if(!isSameParent(weights.get(i).x, weights.get(i).y)){
                    union(weights.get(i).x, weights.get(i).y); // 연결하기
                    ans = ans + weights.get(i).weight; // weight 구하기
                }
            }
            System.out.format("#%d %.0f\n", test, ans);
        }

        br.close();
    }

    // 부모가 같은지 확인
    public static boolean isSameParent(int x, int y){
        x = findParent(x);
        y = findParent(y);
        if(x != y) return false;

        return true;
    }

    // x의 부모를 찾는 func
    public static int findParent(int x){
        if(parent[x] == x) return x;
        else
            return parent[x] = findParent(parent[x]);
    }

    // 부모가 다르다면 연결해주는 func
    public static void union(int x, int y){
        // 부모 찾기
        x = findParent(x);
        y = findParent(y);

        // 부모가 다르다면 연결되어 있지 않은 상태
        if(x != y){
            parent[y] = x; //  연결
        }
    }

    // weight 계산
    public static double calWeight(long x, long y, long dx, long dy){        
        return E * Math.pow(Math.sqrt(Math.pow(dx-x, 2) + Math.pow(dy-y, 2)),2);
    }
}