[백준, JAVA]10021번, Watering the Fields

문제 링크

10021번: Watering the Fields

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

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

---

문제 설명

---

 

접근 방법

최소 신장 트리

신장 트리 : 어떤 그래프에 대하여 모든 꼭짓점을 포함하는부분 그래프입니다.

 

최소 신장 트리 : 신장 트리에서 최소의 가중치를 가지는 부분 그래프입니다. 

Minimum spanning tree - Wikipedia

최소 신장 트리를 구하기 위해서 Union-Find 알고리즘을 이용하여 구현하였습니다.

Union Find - 나무위키

 

이 문제에 핵심은

1. 파이프를 설치하는 좌표와 N, C을 입력받습니다.

2. 파이프 설치의 비용은 문제에서 설명한 점화식으로 구합니다.

3. 파이프를 설치할 때 비용이 C미만이면 설치할 수 없습니다.

4. 각 설치 지점을 지나는 파이프를 설치할 때 최소 비용을 결과로 출력합니다.

5. 만약 파이프 망을 설치하지 못할 경우 -1을 결과로 출력합니다.

 

브루트포스 형식으로 각 좌표끼리에 파이프 설치 경우를 구합니다.

 

※파이프 설치의 비용이 C미만인 경우에는 해당 파이프는 설치하지 못합니다.

 

각 파이프 설치에 대한 비용에 따라 오름차순 정렬을 하였습니다.

 

파이프을 탐색할 때 Union-Find를 이용하여 사이클이 발생하는지 확인하여 최소 신장 트리를 완성하였습니다.

 

해당 최소 신장 트리에 대한 가중치를 결과로 출력합니다.

 

※최소 신장 트리가 만들어지지 않는다면 -1을 결과로 출력합니다.

 

 

예제입력 1.

N = 3, C = 11

1번 좌표 : (0, 2)

2번 좌표 : (5, 0)

3번 좌표 : (4, 3)

C보다 작은 비용의 파이프는 설치할 수 없습니다.

 

파이프에 대하여 비용에 대하여 오름차순 정렬한다.

Union-Find에 사용할 Root

1	2	3
1	2	3

 

가장 작은 비용의 파이프 탐색

1	2	3
1	2	1

다음 작은 파이프 탐색

1	2	3
1	1	1

Root의 값이 모두 같아졌기 때문에 최소 신장 트리 완성!!

 

최소 신장 트리 가중치 : 46 

 

결과 46을 출력

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 N, C와 파이프 설치 좌표를 저장하였습니다.
• 브루트 포스로 모든 파이프 설치 경우를 구하는 makeNode함수를 실행하였습니다.
• Collections.sort를 이용하여 파이프 비용 관련 오름차순 정렬하였습니다.
• Union-Find를 이용하여 최소 신장 트리를 구하여서 모든 좌표를 지나는지 확인하였습니다.
• 모든 좌표를 지나면 최소 신장트리의 가중치, 지나지 않으면 -1을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• makeNode함수는 브루트 포스로 비용이 C 미만인 파이프 경우를 모두 구하였습니다.
• find함수는Root 노드를 구하는 함수입니다. 
• union함수는 Root 노드를 비교 및 변경하는 함수입니다.
• pipeWidthCal함수는 문제에 설명한 점화식으로 파이프 설치 비용을 구하는 함수입니다.
• lineLimitCheck함수는 해당 파이프의 설치 비용이 C보다 작은지 확인하는 함수입니다.

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

public class Main {
    //파이프의 설치 관련 좌표 클래스
    static class position{
        int x, y;
        public position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    //설치된 파이프 관련 클래스
    static class node{
        int f1, f2, value;
        public node(int f1, int f2, int value) {
            this.f1 = f1;
            this.f2 = f2;
            this.value = value;
        }
    }
    static int N,C;
    static int[] root;		//Union-Find 관련 root 배열
    static ArrayList<position> field = new ArrayList<>();	//좌표 저장 리스트
    static ArrayList<node> line = new ArrayList<>();	//파이프 관련 저장 리스트
    static public void  main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        root = new int[N];
        //root 배열 초기화
        for(int i=0;i<N;i++)
            root[i] = i;
        //설치 좌표 저장
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            field.add(new position(x, y));
        }
        makeNode();		//브루트포스로 설치 가능한 모든 파이프 구하기
        //파이프 설치 비용 관련 오름차순 정렬
        Collections.sort(line, new Comparator<node>() {
            @Override
            public int compare(node o1, node o2) {
                return o1.value-o2.value;
            }
        });
        int result = 0;
        //최소 신장 트리 만들기
        for(int i=0;i<line.size();i++){
            int f1 = line.get(i).f1;
            int f2 = line.get(i).f2;
            int value = line.get(i).value;
            if(union(f1, f2)){
                result += value;
            }
        }
        //모든 좌표가 연결되었는지 확인
        for(int i=0;i<N;i++){
            if(find(i) != 0){
                result = -1;
                break;
            }
        }
        bw.write(result + "\n");		//최소 신장 트리 가중치 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //Union-Find에서 Root 노드 찾는 함수
    static int find(int n){
        if(root[n] == n)
            return n;
        return root[n] = find(root[n]);
    }
    //Union-Find에서 Root 노드 변경 및 비교 함수
    static boolean union(int a, int b){
        int x = find(a);
        int y = find(b);
        if(x!=y){
            if(x>y)
                root[x] = y;
            else
                root[y] = x;
            return true;
        }
        return false;
    }
    //브루트포스로 모든 파이프의 경우 만드는 함수
    static void makeNode(){
        int size = field.size();
        for(int i=0;i<size;i++){
            for(int j=i+1;j<size;j++){
                int width = pipeWidthCal(field.get(i), field.get(j));
                if(lineLimitCheck(width))
                    line.add(new node(i,j,width));
            }
        }
    }
    //파이프 설치 비용을 계산하는 함수
    static int pipeWidthCal(position p1, position p2){
        return (int)(Math.pow(p1.x-p2.x,2) + Math.pow(p1.y-p2.y,2));
    }
    //파이프 설치 비용이 C보다 작은지 확인하는 함수
    static boolean lineLimitCheck(int value){
        if(value>=C)
            return true;
        return false;
    }
}