20955 민서의 응급 수술(C++)
https://www.acmicpc.net/problem/20955
학생이 졸다가 머리를 박아서 뇌손상이 왔다고한다
머리의 시냅스가 끊어져 혼수상태에 빠졌는데
이를 트리 형태로 연결하면 깨울수 있다고 한다
1. 문제
간단 설명
뉴런을 노드로 시냅스를 에지로 변환하면
일반적인 그래프 문제가 된다
N개의 노드 개수와 M개의 에지 개수가 주어진다
이후 M개의 에지 정보가 주어질 때,
모든 뉴런을 트리 형태로 연결하기 위해 필요한 최소 연산 회수를 구하는 문제
2. 문제 분석
주의점
주어진 에지 정보는 순환 그래프일 수도 있다. 트리 변환을 위해선 이를 끊어야함
입력의 양이 방대하므로 빠른 입력을 사용할 것을 권장함
알고리즘
-1. 첫번째로 시도해본 방법
그래프 덩어리 별로 묶여있으므로, union-find 알고리즘을 사용해봄
전체 그룹 개수를 구하고, 그 그룹들을 서로 묶으면 되는거 아닌가 싶어 도전했으나 실패.
“트리 형태”로 변환해야한다는 조건에 걸림.
이를 위해서는 사이클이 존재하는지 확인하는 조건이 필요하다
-2. 두번째로 시도해본 방법
- union-find 알고리즘을 사용하되, 사이클이 존재하는지를 체크하는 과정 추가
1
2
3
4
5
6
7
8
9
10
11
12
1. N과 M을 입력받는다
2. union-find를 위해 배열을 초기화 해준다
3. M개의 에지 연결 정보를 입력받는다
3-1. 노드 a, b를 입력받는다
3-2. a와 b의 부모가 다르다면(같은 그룹이 아님) 같은 그룹으로 묶어준다
3-3. 부모가 같다면 사이클이 발생한 것이므로, 사이클 변수에 1을 추가해준다
- 이미 같은 그룹으로 묶여있는 상황인데, 또 연결 정보가 주어진 것이므로, 사이클이 형성된 것!
- 사이클만 추가하고, 그룹형성은 따로하지 않음
4. 전체 그룹 개수가 몇개인지 체크한다
5. (전체 그룹의 개수 - 1) + (사이클 개수)를 출력한다
- 전체 그룹의 개수 - 1 : 전체 그룹개수들을 연결하는 에지 개수
- 사이클 개수 : 사이클이 생성됬을 때, 에지 연결을 끊어 트리로 만들어야 하므로 그만큼의 연산회수가 추가됨
필요변수
노드 개수
int N(2 ≤ N ≤ 100,000)에지 개수
int M(1 ≤ M ≤ min(N × (N – 1) / 2, 100,000))에지 연결 정보
int a, bunion-find를 위한 부모 정보를 저장하는 배열
int arr[MAX]findboss, setUnion 함수
사이클의 개수
int cycle전체 그룹의 개수
int ans
3. 소스코드
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
#include <iostream>
using namespace std;
int N, M;
int arr[100001];
int cycle = 0;
int ans = 0;
// 노드의 부모를 찾는 함수
int findBoss(int target) {
if (arr[target] == target)
return target; // 만약 부모가 자기 자신이라면 그 노드가 부모임
return arr[target] = findBoss(arr[target]);
}
// 노드를 묶는 함수
void setUnion(int a, int b) {
int aboss = findBoss(a);
int bboss = findBoss(b);
// b의 부모를 a의 부모로 설정한다
if (aboss != bboss)
arr[bboss] = aboss;
}
int main() {
freopen_s(new FILE*, "input.txt", "r", stdin);
scanf("%d %d", &N, &M);
// union-find 초기화 : 자기 자신으로 부모를 초기화 시켜둠
for (int i = 0; i <= N; i++)
arr[i] = i;
// m개의 에지를 입력받는다
while(M--) {
int a, b;
scanf("%d %d", &a, &b);
// a와 b를 입력받고 부모가 다르다면, 묶어준다
if (findBoss(a) != findBoss(b)) {
setUnion(a, b);
}
// 부모가 같다면? 사이클 발생이므로, 사이클 개수 증가
else {
cycle++;
}
}
for (int i = 1; i <= N; i++) {
if (arr[i] == i) ans++;
}
//
printf("%d\n", ans - 1 + cycle);
return 0;
}
findBoss 부분에서
1
2
3
4
5
6
7
8
// 노드의 부모를 찾는 함수
int findBoss(int target) {
if (arr[target] == target)
return target; // 만약 부모가 자기 자신이라면 그 노드가 부모임
int boss = findBoss(arr[target]);
// arr[target] = boss;
return boss;
}
로 시도하니 시간초과가 발생하였다
이를
1
2
3
4
5
6
// 노드의 부모를 찾는 함수
int findBoss(int target) {
if (arr[target] == target)
return target; // 만약 부모가 자기 자신이라면 그 노드가 부모임
return arr[target] = findBoss(arr[target]);
}
로 수정하니 통과되었는데, 어떤 차이가 있는지 더 알아봐야겠다
참고한 링크