백준_Count Circle Groups_그래프

백준_Count Circle Groups_그래프_10216(Java)

2019. 3. 22. 17:08ㆍ알고리즘문제/백준

Count Circle Groups

1. 문제

https://www.acmicpc.net/problem/10216

2차원 평면 위의 N곳에 적군의 진영이 설치되어 있다. 각 적군의 진영들은 마다마다 하나의 통신탑을 설치해, i번째 적군의 통신탑은 설치 위치로부터 Ri 이내 거리에 포함되는 모든 지역을 자신의 통신영역 Ai로 가지게 된다. 만약 임의의 통신영역 Ai와 Aj가 닿거나 겹치는 부분이 있다면 진영 i와 진영 j는 직접적으로 통신이 가능하다. 물론 직접적으로 통신이 가능하지 않더라도, 임의의 지역 i와 j가 중간에 몇 개의 직접통신을 거쳐서 최종적으로 통신이 가능하다면 i와 j는 상호간에 통신이 가능한 것으로 본다.

적들은 영리해서, 상호간에 통신이 가능한 부대끼리는 결집력있는 한 그룹처럼 행동한다. 백준은 이러한 그룹의 개수를 알아내 아군의 전략지침에 도움을 주고자 한다. 군대에 가서도 코딩하는 불쌍한 백준을 위해 적군의 통신망 분석을 도와주자!

solution - 1) 그래프의 인접리스트 이용 (ArrayList) / (BFS)

1. Point 클래스 생성

2. Point정보를 담은 ArrayList 생성

3. visit[] 배열을 이용해 방문한 노드를 다시 방문하지 않게하여 효율성을 높인다.

다른 블로그 코드를 참조하였다. (똑같..) . 엄청 깔끔하다.

내가 헤맸던 부분 : 26 ~ 56

1. 먼저 방문하지 않은 노드 먼저 확인한다. (cnt 는 그룹의 개수)

2. 방문하면서 true로 바꿔주고 Bfs함수 시작, cnt ++

3. 큐 생성. 연결된 모든 노드를 탐색하면서 visit을 true로 바꿔준다. -> 하나의 그룹 내를 모두 탐색하는것.

4. 함수가 끝나고 나면 다음에는 그 다음 그룹을 탐색하는 방법이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        sc.nextLine();
        for (int i = 0; i < T; i++) {
            int N = sc.nextInt();
            sc.nextLine();
 
            ArrayList<Point> list = new ArrayList<Point>();
 
            for (int j = 0; j < N; j++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                int r = sc.nextInt();
                sc.nextLine();
                
                list.add(new Main().new Point(x, y, r));
                
            }
            boolean[] visit = new boolean[list.size()];
            int cnt = 0;
            for(int j = 0; j < list.size(); j++){
                if(!visit[j]) {
                    visit[j] = true;
                    bfs(list, j, visit);
                    cnt++;
                }
            }
 
            System.out.println(cnt);
        }
        sc.close();
 
    }
 
    private static void bfs(ArrayList<Point> list, int s, boolean[] visit) {
        Queue<Point> temp = new LinkedList<Point>();
        temp.add(list.get(s));
        
        while(!temp.isEmpty()) {
            Point standard = temp.poll();
            for(int i = 0; i < list.size(); i++) {
                if(!visit[i] && standard.isContinous(list.get(i))) {
                    visit[i] = true;
                    temp.add(list.get(i));
                }
            }
        }
        
    }
 
    public class Point {
        private int x;
        private int y;
        private int r;
 
        public Point(int x, int y, int r) {
            this.x = x;
            this.y = y;
            this.r = r;
        }
 
        public boolean isContinous(Point point) {
            return Math.sqrt(Math.pow(this.x - point.x, 2) + Math.pow(this.y - point.y, 2)) <= this.r + point.r;
        }
    }
 
}
 
Colored by Color Scripter
cs

* 한 파일 내에 두 클래스가 사용될 경우 (Main과 Point)

Main 내에서 Point 클래스를 사용하려면 new Main.new Point 이렇게 선언해야 한다. ... 대박 !

mine) 그래프의 인접리스트 이용 (ArrayList) / (DFS)

아래 코드는

새롭게 들어오는 군지역이 앞서 분리되어 있던 두 그룹을 합칠 수 있는 경우를 생각하지 못해 틀렸다.

해당 방법만 알아낼 수 있었으면... 또륵

import java.util.ArrayList;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        sc.nextLine();
        for(int i = 0 ; i < T; i++) {
            int N = sc.nextInt();
            sc.nextLine();
            
            int[] x = new int[N];
            int[] y = new int[N];
            int[] r = new int[N];
            
            int count = 1; 
            boolean ch = false;
            for(int j = 0; j < N; j++) {
                x[j] = sc.nextInt();
                y[j] = sc.nextInt();
                r[j] = sc.nextInt();
                sc.nextLine();
                
                if(j > 0) {
                    for(int s = 1; s <= j; s++) {
                        double distance = dist(x[j-s], y[j-s], x[j], y[j]);
                        if(distance <= r[j-s] + r[j]) {
                            ch = true;
                        }
                        
                    }
                    if(!ch){
                        count++;
                    }
                    ch = false;
                }
            }        
            System.out.println(count);        
        }
        
 
    }
    
    public static double dist(int x1, int y1, int x2, int y2) { // 두 점 사이의 거리 
        return Math.sqrt(Math.pow(Math.abs(x1-x2), 2) + Math.pow(Math.abs(y1-y2),2));
    }
 
}
 

Colored by Color Scripter

위 코드 수정해서 성공했다 !!!!!!!!!

solution - 2) 그래프의 인접리스트 이용 (ArrayList) / (DFS)

solution1보다 메모리 사용량이나 시간이 조금 더 들지만 그래도 성공 ㅜㅜ!! 행복

DFS는 이렇게 하는건가보다 !!!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import java.util.ArrayList;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        sc.nextLine();
        for(int i = 0 ; i < T; i++) {
            int N = sc.nextInt();
            sc.nextLine();
            
            int[] x = new int[N];
            int[] y = new int[N];
            int[] r = new int[N];
            
            ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
            
            int cnt = 0;
            
            for(int j = 0; j < N; j++) {
                list.add(new ArrayList<Integer>());
                x[j] = sc.nextInt();
                y[j] = sc.nextInt();
                r[j] = sc.nextInt();
                sc.nextLine();
                
                if(j > 0) {
                    for(int s = 1; s <= j; s++) {
                        double distance = dist(x[j-s], y[j-s], x[j], y[j]);
                        if(distance <= r[j-s] + r[j]) {
                            list.get(j).add(j-s);
                            list.get(j-s).add(j);
                        }
                        
                    }
                }
                
                
            }
            
            boolean visit[] = new boolean[list.size()];
            for(int s = 0; s < list.size(); s++) {
                if(!visit[s]) {
                    visit[s] = true;
                    Dfs(list, s, visit);
                    cnt++;
                }
            }
            
            System.out.println(cnt);        
            
        }
        sc.close();
 
    }
    
    private static void Dfs(ArrayList<ArrayList<Integer>> list, int s, boolean[] visit) {
        for(int i : list.get(s)) {
            if(!visit[i]) {
                visit[i] = true;
                Dfs(list, i, visit);
            }
        }
        
    }
 
    public static double dist(int x1, int y1, int x2, int y2) { // 두 점 사이의 거리 
        return Math.sqrt(Math.pow(Math.abs(x1-x2), 2) + Math.pow(Math.abs(y1-y2),2));
    }
 
}
Colored by Color Scripter
cs

참고 블로그

https://lkhlkh23.tistory.com/83

https://donggod.tistory.com/90

저작자표시 비영리 변경금지

'알고리즘문제 > 백준' 카테고리의 다른 글

백준_계란으로 계란치기[Java] (0)	2019.04.03
백준_인싸들의 가위바위보[Java] (0)	2019.04.03
백준_피보나치 3_2749(java) (0)	2019.03.09
백준_피보나치함수_(1003)_동적계획법(java) (0)	2019.03.09
백준_1,2,3 더하기_동적계획법(java) (0)	2019.03.05

annotation으로부터 시작한 호기심

annotation으로부터 시작한 호기심

태그

최근글

댓글

공지사항

아카이브

'알고리즘문제 > 백준' 카테고리의 다른 글

관련글

티스토리툴바