[백준, Java] 10216번, Count Circle Groups(Union-Find, 수학)

문제 링크

 

10216번: Count Circle Groups

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

1. 적군의 진영은 2차원 평면에 존재하며, 탐지하는 범위는 원의 형태입니다.

2. 탐지하는 범위가 겹치면 해당 진영끼리는 통신이 가능합니다.

3. 간접적으로 연결된 진영끼리도 통신이 가능합니다.

4. 통신이 가능한 진영끼리 그룹을 형성한다.

5. 진영들이 형성한 그룹의 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 모든 진영을 탐색하여 Union-Find를 통해서 그룹을 형성합니다.

 

3. 형성된 그룹의 개수를 결과로 출력합니다.

 

 

모든 진영 탐색

 

각 진영이 다른 진영과 탐색하는 범위가 같은 곳인지 확인해야 합니다.

 

 

조건식을 통해서 확인 할 수 있습니다.

 

[조건식]

 

진영1의 반지름 + 진영2의 반지름 ≥ 두 진영 원점 사이의 거리

 

원점 사이의 거리를 구하는 공식

 

 

위 조건식을 만족한다면?

 

→ 두 진영은 통신이 가능합니다.

 

 

통신이 가능하다고 판단하면 Union-Find를 진행해서 그룹핑을 진행합니다.

 

Union Find - 나무위키

 

 

예제입력 1.

※ 테스트케이스 2번을 기준으로 보여드리겠습니다.

1. 입력된 정보를 저장합니다.

N(진영의 개수) : 3

2차원 좌표에 따른 진영

Union-Find 배열 값

진영 0	진영 1	진영 2
0	1	2

2. 모든 진영을 탐색하여 Union-Find를 통해서 그룹을 형성합니다.

 

(0, 0)

R : 1

진영을 기준으로 다른 진영과 접하는 곳이 있는지 탐색

 

진영0과 진영1 조건식 적용

 

진영0의 반지름(1) + 진영1의 반지름(1) ≥ 두 진영 원점 사이의 거리(2)

 

2 ≥ 2 : True

 

→ 진영0과 진영1은 통신 가능 → Union 진행 →  그룹 형성 

 

 

진영0과 진영2 조건식 적용

 

진영0의 반지름(1) + 진영2의 반지름(5) ≥ 두 진영 원점 사이의 거리(10)

 

6 ≥ 10 : False

 

→ 진영0과 진영2은 통신 불가능

 

Union-Find 배열 값

진영 0	진영 1	진영 2
0	0	2

 

(2, 0)

R : 1

진영을 기준으로 다른 진영과 접하는 곳이 있는지 탐색

진영1과 진영2 조건식 적용

 

진영1의 반지름(1) + 진영2의 반지름(5) ≥ 두 진영 원점 사이의 거리(10)

 

6 ≥ 10 : False

 

→ 진영1과 진영2은 통신 불가능

 

Union-Find 배열 값

진영 0	진영 1	진영 2
0	0	2

 

3. 형성된 그룹의 개수를 결과로 출력합니다.

 

 

형성된 그룹

 

진영0 + 진영1 : 그룹1

 

진영2 : 그룹2

 

그룹의 개수 2을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 진영의 정보들을 띄어쓰기 기준으로 나누었습니다.
• 각 진영별 탐색이 가능한지 cirlceMeetCheck()함수를 통해 확인합니다.
• 탐색이 가능하면 union()함수와 find()함수를 이용해서 그룹을 형성합니다.
• 생성된 그룹의 개수를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• cirlceMeetCheck는 두 진영에 조건식을 통해 탐색이 가능한지 확인하는 함수입니다.
• find는 그룹의 부모를 찾는 함수입니다.
• union는 그룹의 부모 기준으로 합쳐지는 함수입니다.
• calTwoCircleLength는 두 원점 사이의 거리를 구하는 함수입니다.

※ 2번에 걸쳐서 시간 복잡도 개선을 진행하였습니다.

결과 코드는 최종 개선한 코드이고,

이전 코드들은 아래에 첨부하였으며 어떤 점을 개선하였는지 설명을 작성해두었습니다.

 

※조건식에 Math.sqrt을 제거하는 과정

양변을 제곱해주면 Math.sqrt를 진행하는 √을 제거할 수 있습니다.

위 조건식으로 탐색을 확인한다면 Math.sqrt를 진행하지 않을 수 있습니다.

결과코드

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

public class Main{
    //parent[] : 그룹의 부모 저장 배열
    //X[],Y[], R[] : 진영의 정보를 저장합니다.
    static int[] parent, X, Y, R;
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //입력값 저장
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;

        for(int test_case = 0;test_case < T;test_case++){
            int N = Integer.parseInt(br.readLine());
            parent = new int[N];
            X = new int[N];
            Y = new int[N];
            R = new int[N];
            //원의 정보 저장
            for(int i=0;i<N;i++){
                parent[i] = i;	//각 그룹의 부모 초기화
                st = new StringTokenizer(br.readLine());
                X[i] = Integer.parseInt(st.nextToken());
                Y[i] = Integer.parseInt(st.nextToken());
                R[i] = Integer.parseInt(st.nextToken());
            }
            int groupCnt= N;
            //각 진영을 기준으로 다른 진영 통신 가능한지 탐색
            for(int i=0;i<N;i++){
                for(int j=i+1;j<N;j++){
                    //두 진영이 통신이 가능할 때
                    if(cirlceMeetCheck(i, j)){
                        //그룹이 만들어지면 N개의 그룹 - 1을 진행합니다.
                        if(union(i, j))
                            groupCnt--;
                    }
                }
            }
            //그룹의 개수 BufferedWriter 저장
            bw.write(String.valueOf(groupCnt));
            bw.newLine();
        }
        bw.flush();		//종합된 결과 출력
        bw.close();
        br.close();
    }
    //그룹의 부모 찾는 함수
    static int find(int a){
        if(parent[a] == a)
            return a;
        return find(parent[a]);
    }
    //부모를 변경함으로써 그룹을 형성하는 함수
    static boolean union(int a, int b){
        int pa = find(a);
        int pb = find(b);
        if(pa == pb)	//부모가 같으면?? 이미 같은 그룹
            return false;
        parent[pb] = pa;	//부모가 다르기 때문에 그룹 형성
        return true;
    }
    //두 진영의 통신이 가능한지 탐색하는 함수입니다.
    static boolean cirlceMeetCheck(int c1_idx, int c2_idx){
        int d = calTwoCircleLength(X[c2_idx] - X[c1_idx], Y[c2_idx] - Y[c1_idx]);
        //두 진영의 반지름 더하기
        int plus = R[c1_idx] + R[c2_idx];
        if(plus * plus >= d)	//조건식에 만족할 때
            return true;
        return false;		//조건식에 만족하지 않을 때
    }
    //진영 두 원점의 거리를 계산하는 함수
    static int calTwoCircleLength(int x_dif, int y_dif){
        return x_dif * x_dif + y_dif*y_dif;
    }
}

개선 전 코드 모음

초기 코드(5424ms)

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

public class Main{
    static class Circle{
        int x, y, r;
        public Circle(int x, int y, int r){
            this.x = x;
            this.y = y;
            this.r = r;
        }
    }
    static int[] parent;
    static boolean[] groupCheck;
    static List<Circle> circles = new ArrayList<>();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int test_case = 0;test_case < T;test_case++){
            int N = Integer.parseInt(br.readLine());
            parent = new int[N];
            for(int i=0;i<N;i++){
                parent[i] = i;
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                int r = Integer.parseInt(st.nextToken());
                circles.add(new Circle(x, y, r));
            }
            int groupCnt= N;
            for(int i=0;i<N;i++){
                for(int j=i+1;j<N;j++){
                    if(cirlceMeetCheck(i, j)){
                        if(union(i, j))
                            groupCnt--;
                    }
                }
            }
            bw.write(String.valueOf(groupCnt));
            bw.newLine();
            circles.clear();
        }
        bw.flush();
        bw.close();
        br.close();
    }
    static int find(int a){
        if(parent[a] == a)
            return a;
        return find(parent[a]);
    }
    static boolean union(int a, int b){
        int pa = find(a);
        int pb = find(b);
        if(pa == pb)
            return false;
        parent[pb] = pa;
        return true;
    }
    static boolean cirlceMeetCheck(int c1_idx, int c2_idx){
        Circle c1 = circles.get(c1_idx);
        Circle c2 = circles.get(c2_idx);
        double d = calTwoCircleLength(c1.x, c1.y, c2.x, c2.y);
        if(c1.r + c2.r >= d)
            return true;
        return false;
    }
    static double calTwoCircleLength(int x1, int y1, int x2, int y2){
        return Math.sqrt(Math.pow(x2-x1, 2) + Math.pow(y2-y1, 2));
    }
}

개선사항 : Math.sqrt() 제거, Math.pow() 대신 * 을 사용해서 곱하기로 변경

 

1차 개선 코드(3696ms)

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

public class Main{
    static class Circle{
        int x, y, r;
        public Circle(int x, int y, int r){
            this.x = x;
            this.y = y;
            this.r = r;
        }
    }
    static int[] parent;
    static boolean[] groupCheck;
    static List<Circle> circles = new ArrayList<>();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int test_case = 0;test_case < T;test_case++){
            int N = Integer.parseInt(br.readLine());
            parent = new int[N];
            for(int i=0;i<N;i++){
                parent[i] = i;
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                int r = Integer.parseInt(st.nextToken());
                circles.add(new Circle(x, y, r));
            }
            int groupCnt= N;
            for(int i=0;i<N;i++){
                for(int j=i+1;j<N;j++){
                    if(cirlceMeetCheck(i, j)){
                        if(union(i, j))
                            groupCnt--;
                    }
                }
            }
            bw.write(String.valueOf(groupCnt));
            bw.newLine();
            circles.clear();
        }
        bw.flush();
        bw.close();
        br.close();
    }
    static int find(int a){
        if(parent[a] == a)
            return a;
        return find(parent[a]);
    }
    static boolean union(int a, int b){
        int pa = find(a);
        int pb = find(b);
        if(pa == pb)
            return false;
        parent[pb] = pa;
        return true;
    }
    static boolean cirlceMeetCheck(int c1_idx, int c2_idx){
        Circle c1 = circles.get(c1_idx);
        Circle c2 = circles.get(c2_idx);
        int d = calTwoCircleLength(c2.x - c1.x, c2.y - c1.y);
        int plus = c1.r + c2.r;
        if(plus * plus >= d)
            return true;
        return false;
    }
    static int calTwoCircleLength(int x_dif, int y_dif){
        return x_dif * x_dif + y_dif*y_dif;
    }
}

 

개선사항 : InnerClass Circle을 ArrayList<>()로 사용하였다면, X[], Y[], R[]으로 변경하였습니다.

접근성의 시간복잡도가 더 뛰어난 배열[]을 사용하여 개선하였습니다.

 

개선한 코드는 결과 코드입니다.