[백준] 10216번 C/C++ 풀이 _ Count Circle Groups

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

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
8 초	256 MB	3259	835	589	26.579%

문제

백준이는 국방의 의무를 수행하기 위해 떠났다. 혹독한 훈련을 무사히 마치고 나서, 정말 잘 생겼고 코딩도 잘하는 백준은 그 특기를 살려 적군의 진영을 수학적으로 분석하는 일을 맡게 되었다.

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

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

입력

입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.

각각의 테스트 케이스에 대해서 적군 진영의 숫자 N (1 ≤ N ≤ 3,000)이 주어진다. 이어서 N줄에 걸쳐 적군 진영의 좌표 x, y (0 ≤ x, y ≤ 5,000), 그리고 해당 진영의 R (0 ≤ R ≤ 5,000)이 주어진다. 주어지는 수는 모두 정수이다.

출력

각 테스트 케이스에 대해서 한 줄에 걸쳐 적군 진영의 그룹 갯수를 출력한다.

예제 입력

예제 출력

1
2

힌트

출처

Contest > Coder's High > Coder's High 2014 C번

문제를 만든 사람: tae

>> 문제 해설

이번에는 문제를 풀 때, 연결 리스트를 이용하여 트리를 사용하지 않고 배열을 이용해보았다.

위와 같은 구조체를 생성한다.
구조체 배열을 크기가 3000가 되게 생성한 다음에, 입력으로 주어진 x, y, R 을 차례대로 입력받는다.

모든 입력을 받아서 for 문을 통해서 돌면서, 두 점 사이의 거리가 반지름의 합보다 작거나 같으면 connection 관계를 형성시켜준다.
이 과정에서 시간 복잡도는 O(N2)이다.

그 다음에는 0번 인덱스 부터 N번 인덱스까지 for 문을 통해서 연결된 노드들을 판단한다.
만약, 방문한 노드가 아니면 queue 에 추가해준다.
while문을 queue 사이즈가 0보다 클 때 동안 계속해서 수행한다.
queue 에서 뺀 노드들에 연결된 노드들이 방문한 노드가 아니면 queue 에 또 추가해준다.
위와 같은 과정을 반복해서 문제를 해결한다.

한 인덱스에서 방문한 노드들을 검색하는 경우는 N개이고 N개의 노드들이 모두 N번씩 방문한 노드들을 검색한다고 가정하면

O(N2)이다. N 이 작기 때문에 이 정도는 무난하게 통과할 수 있는 속도이다.

문제 풀이 하던 도중에 malloc 을 쓰다가 메모리 초과가 발생했다.
똑같은 구조인데 이번에는 한 번에 여러 가지 테스트 케이스를 진행해서 문제가 발생했다.
메모리 해제를 할 때, 주의할 점은 이중 배열 같은 경우에는 for문을 돌면서 두 번째 인덱스를 가진 항목을 먼저 해제해주고 마지막에 최종 변수를 해제해야 한다.

해당 소스코드는 아래에 별도로 첨부한다.

>> 소스 코드

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>  
#include <queue>
 
using namespace std;
 
int T, N;
 
typedef struct TOWER {
    int x;
    int y;
    int R;
};
 
// 타워 정보 입력 받는 배열
TOWER tower_arr[3000];
// 방문한 노드를 표현하는 배열
int visited[3000];
// 연결 여부를 표현하는 배열
int connection[3000][3000];
 
int main() {
    cin >> T;
 
    for (int i = 0; i < T; i++) {
        cin >> N; 
 
        // 방문한 노드 초기화 
        for (int j = 0; j < N; j++)  visited[j] = 0;
    
        // 연결 초기화 
        for (int j = 0; j < N; j++) 
            for (int k = 0; k < N; k++) 
                connection[j][k] = 0;
            
        // 정보 입력 받기 
        int sub_x, sub_y, sub_R;
        for (int j = 0; j < N; j++){
            scanf("%d %d %d", &sub_x, &sub_y, &sub_R );
            tower_arr[j] = TOWER{ sub_x , sub_y , sub_R  };
        }
 
        // 거리 검사 후 관계 형성
        for (int j = 0; j < N; j++) {
            for (int k = j+1; k < N; k++) {
                int min_x = ((tower_arr[j].x) - (tower_arr[k].x));
                int min_y = ((tower_arr[j].y) - (tower_arr[k].y));
                int sum_R = ((tower_arr[j].R) + (tower_arr[k].R));
 
                // 만약 닿거나 공통된 부분이 있으면  
                if ( (min_x*min_x + min_y*min_y) <= (sum_R*sum_R) ) {
                    connection[j][k] = 1;        connection[k][j] = 1;
                }
 
            }
        }
 
        // 싸이클 확인
        int cycle_num = 0 ;
        queue<int> confirm_queue; 
 
        for (int j = 0; j < N; j++) {
            // 방문하지 않았으면 싸이클을 1 추가하고, 싸이클을 체크한다. 
            if ( visited[j] == 0){
                cycle_num++;
                visited[j] = 1;
                confirm_queue.push(j);
                // queue 에 숫자가 없을 때 까지 while 문을 반복한다. 
                while ( confirm_queue.size() ) {
                    int sub_index = confirm_queue.front();
                    confirm_queue.pop();
                    // queue에서 빼낸 index에서 k를 0부터 시작하면서, 연결된 인덱스를 확인.
                    // 인덱스가 1로 연결되어있고, visited도 0이면 queue에 추가해준다. 
                    for (int k = 0; k < N; k++) {
                        if (connection[sub_index][k] == 1 && visited[k] == 0){
                            visited[k] = 1;
                            confirm_queue.push(k);
                        } 
                    }
                }
 
            }
        }
 
        // 정답 출력 
        cout << cycle_num << "\n";
    }
 
    return 0; 
}
Colored by Color Scripter
cs

>> 틀린 소스코드

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
 
using namespace std;
 
int T, N;
 
typedef struct TOWER {
    int x;
    int y;
    int R;
};
 
// 타워 정보 입력 받는 배열
TOWER** tower_arr;
// 방문한 노드를 표현하는 배열
int* visited;
// 연결 여부를 표현하는 배열
int** connection;
 
int main() {
    cin >> T;
 
    for (int i = 0; i < T; i++) {
        cin >> N; 
 
        tower_arr = (TOWER**)malloc(sizeof(TOWER*)*N);
        visited = (int*)malloc(sizeof(int)*N);
        connection = (int**)malloc(sizeof(int*)*N);
 
        // 방문한 노드 초기화 
        for (int j = 0; j < N; j++) {
            visited[j] = 0;
            connection[j] = (int*)malloc(sizeof(int)*N);
        }
 
        // 연결 초기화 
        for (int j = 0; j < N; j++)
            for (int k = 0; k < N; k++)
                connection[j][k] = 0;
            
        // 정보 입력 받기 
        int sub_x, sub_y, sub_R;
        for (int j = 0; j < N; j++){
            scanf("%d %d %d", &sub_x, &sub_y, &sub_R );
            tower_arr[j] = (TOWER*)malloc(sizeof(TOWER));
            tower_arr[j]->x = sub_x;
            tower_arr[j]->y = sub_y;
            tower_arr[j]->R = sub_R;
        }
 
        // 거리 검사 후 관계 형성
        for (int j = 0; j < N; j++) {
            for (int k = j+1; k < N; k++) {
                int min_x = ((tower_arr[j]->x) - (tower_arr[k]->x));
                int min_y = ((tower_arr[j]->y) - (tower_arr[k]->y));
                int sum_R = ((tower_arr[j]->R) + (tower_arr[k]->R));
                
 
                // 만약 닿거나 공통된 부분이 있으면  
                if ( (min_x*min_x + min_y*min_y) <= (sum_R*sum_R) ) {
                    connection[j][k] = 1;        connection[k][j] = 1;
                }
 
            }
            free(tower_arr[j]);
        }
 
        // 싸이클 확인
        int cycle_num = 0 ;
        queue<int> confirm_queue; 
 
        for (int j = 0; j < N; j++) {
            // 방문하지 않았으면 싸이클을 1 추가하고, 싸이클을 체크한다. 
            if ( visited[j] == 0){
                cycle_num++;
                visited[j] = 1;
                confirm_queue.push(j);
                // queue 에 숫자가 없을 때 까지 while 문을 반복한다. 
                while ( confirm_queue.size() ) {
                    int sub_index = confirm_queue.front();
                    confirm_queue.pop();
                    // 0번 인덱스 부터 시작하면서, queue에서 빼낸 index에서 연결된 인덱스를 확인한다.
                    // 인덱스가 1로 연결되어있고, visited도 0이면 queue에 추가해준다. 
                    for (int k = 0; k < N; k++) {
                        if (connection[sub_index][k] == 1 && visited[k] == 0){
                            visited[k] = 1;
                            confirm_queue.push(k);
                        } 
                    }
                }
 
            }
        }
 
        // 정답 출력 
        cout << cycle_num << "\n";
 
        // 메모리 해제 
        free(tower_arr);
        free(visited);
        free(connection);
    }
 
    return 0; 
}
Colored by Color Scripter
cs

>> 수정된 소스코드

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
 
using namespace std;
 
int T, N;
 
typedef struct TOWER {
    int x;
    int y;
    int R;
};
 
// 타워 정보 입력 받는 배열
TOWER** tower_arr;
// 방문한 노드를 표현하는 배열
int* visited;
// 연결 여부를 표현하는 배열
int** connection;
 
int main() {
    cin >> T;
 
    for (int i = 0; i < T; i++) {
        cin >> N; 
 
        tower_arr = (TOWER**)malloc(sizeof(TOWER*)*N);
        visited = (int*)malloc(sizeof(int)*N);
        connection = (int**)malloc(sizeof(int*)*N);
 
        // 방문한 노드 초기화 
        for (int j = 0; j < N; j++) {
            visited[j] = 0;
            connection[j] = (int*)malloc(sizeof(int)*N);
        }
 
        // 연결 초기화 
        for (int j = 0; j < N; j++)
            for (int k = 0; k < N; k++)
                connection[j][k] = 0;
            
        // 정보 입력 받기 
        int sub_x, sub_y, sub_R;
        for (int j = 0; j < N; j++){
            scanf("%d %d %d", &sub_x, &sub_y, &sub_R );
            tower_arr[j] = (TOWER*)malloc(sizeof(TOWER));
            tower_arr[j]->x = sub_x;
            tower_arr[j]->y = sub_y;
            tower_arr[j]->R = sub_R;
        }
 
        // 거리 검사 후 관계 형성
        for (int j = 0; j < N; j++) {
            for (int k = j+1; k < N; k++) {
                int min_x = ((tower_arr[j]->x) - (tower_arr[k]->x));
                int min_y = ((tower_arr[j]->y) - (tower_arr[k]->y));
                int sum_R = ((tower_arr[j]->R) + (tower_arr[k]->R));
                
 
                // 만약 닿거나 공통된 부분이 있으면  
                if ( (min_x*min_x + min_y*min_y) <= (sum_R*sum_R) ) {
                    connection[j][k] = 1;        connection[k][j] = 1;
                }
 
            } 
        }
 
        // 싸이클 확인
        int cycle_num = 0 ;
        queue<int> confirm_queue; 
 
        for (int j = 0; j < N; j++) {
            // 방문하지 않았으면 싸이클을 1 추가하고, 싸이클을 체크한다. 
            if ( visited[j] == 0){
                cycle_num++;
                visited[j] = 1;
                confirm_queue.push(j);
                // queue 에 숫자가 없을 때 까지 while 문을 반복한다. 
                while ( confirm_queue.size() ) {
                    int sub_index = confirm_queue.front();
                    confirm_queue.pop();
                    // 0번 인덱스 부터 시작하면서, queue에서 빼낸 index에서 연결된 인덱스를 확인한다.
                    // 인덱스가 1로 연결되어있고, visited도 0이면 queue에 추가해준다. 
                    for (int k = 0; k < N; k++) {
                        if (connection[sub_index][k] == 1 && visited[k] == 0){
                            visited[k] = 1;
                            confirm_queue.push(k);
                        } 
                    }
                }
 
            }
        }
 
        // 정답 출력 
        cout << cycle_num << "\n";
 
        // 메모리 해제 
        // 거리 검사 후 관계 형성
        for (int j = 0; j < N; j++) {
            free(connection[j]);
            free(tower_arr[j]);
        }
 
 
        free(tower_arr);
        free(visited);
        free(connection);
    }
 
    return 0; 
}
Colored by Color Scripter
cs

PREVIOUS[백준] 1890번 C/C++ 풀이 _ 점프

NEXT[백준] 11657번 C/C++ 풀이 _ 타임머신

Count Circle Groups 성공

문제

입력

출력

예제 입력 복사

예제 출력 복사

힌트

출처

예제 입력

예제 출력