이번 문제는 백준의 골드 4 문제 민서의 응급 수술 문제이다.
문제를 한 번 차근차근 읽어보자.
대충 문제를 훑어보니, 뉴런들을 트리 형태로 연결하고 싶다고 한다.
그 말은, 시냅스들로 사이클 없이 모든 뉴런을 연결하고 싶다는 말이다.
사이클 없이 모두 연결된 트리..? 신장 트리 얘기인 것 같다.
다른 조건은 최대 100000개의 노드, 100000개의 간선이 주어진다.
조건만 보았을 땐, 신장 트리를 만드는 방법을 구현하는 것 같다.
그런데 조건에 중요한 부분이 하나 보인다.
시냅스를 제거할 수 있다. 라는 조건이 문제에 있는데,
그 말은 사이클이 존재할 때 시냅스를 제거해서도 트리를 만들 수 있다는 말이다.
즉, 사이클이 존재한다면 끊어내는 동작도 구현해야 한다는 말이다.
해당 동작을 어떻게 구현할 지가 관건일 것 같다.
Kruskal 알고리즘
우선, 기본적으로 신장 트리를 구현하는 알고리즘으로는
Kruskal 알고리즘을 사용하도록 할 것이다.
원래는 최소 신장 트리를 구하는 알고리즘이지만, 기본적인 원리로
신장 트리를 구할 수 있기 때문에 사용하도록 한다.
기본적으로 union 동작을 통해서 미완성 트리를 완성할 수 있다.
하지만 문제는 이미 사이클이 생겨버린 상태에서 어떻게 끊는가? 이다.
사이클 체크
사이클에 대한 검사는 어떤 두 노드의 부모를 검사했을 때,
두 노드가 같은 부모를 두고 있다면 union을 하면 사이클이 생긴다.
그래서 항상 사이클을 체크해서 사이클이 생기는 것을 방지하도록 한다.
최초에 간선을 입력받을 때, 사이클을 검사하여 가능성이 있으면 배제한다.
이 동작을 사이클을 끊는 것으로 간주하여 동작 횟수를 늘려준다.
이제 남은 일은 연결되지 않은 노드를 연결하는 것!
남은 노드 연결
남은 노드 중 연결되지 않은 노드는 어떤 상태일까?
연결이 되지 않았으므로 부모 노드가 자기 자신으로 설정되어 있을 것이다.
그럼 트리 배열을 돌아, 가장 처음 연결되지 않은 부분을 루트로 삼자.
마저 탐색하다 만나는 나머지 연결되지 않은 부분들을 모두 루트에 연결한다.
그렇다면 사이클 없이 모든 트리가 연결될 것이다.
구현
아래와 같이 전체 코드를 구현했다.
int vertex = 0, edge = 0, from = 0, to = 0, answer = 0;
int nervous_system[100001];
void init_spanning_tree() {
for (int i = 0; i <= vertex; i++)
nervous_system[i] = i;
}
int find_parent(int node) {
if (nervous_system[node] == node)
return node;
return nervous_system[node] = find_parent(nervous_system[node]);
}
void do_union(int node_x, int node_y) {
node_x = find_parent(node_x);
node_y = find_parent(node_y);
if (node_x > node_y)
nervous_system[node_x] = node_y;
else
nervous_system[node_y] = node_x;
}
bool check_cycle(int node_x, int node_y) {
node_x = find_parent(node_x);
node_y = find_parent(node_y);
if (node_x == node_y)
return true;
return false;
}
int main() {
cin >> vertex >> edge;
init_spanning_tree();
for (int i = 0; i < edge; i++) {
cin >> from >> to;
if (!check_cycle(from, to))
do_union(from, to);
else
answer++;
// 주어진 스냅스가 싸이클 가능성이 있으면?
// union 하지 않고 답에 추가
}
int root = 0;
bool get_root = false;
// 이제 남은 연결되지 않은 부분을 모두 이어야 한다.
// 신장트리가 되려면, 루트는 단 하나여야 한다.
for (int i = 1; i <= vertex; i++) {
if (nervous_system[i] == i && !get_root) {
root = i;
get_root = true;
}
else if (nervous_system[i] == i && get_root) {
// 루트가 아닌데 연결이 안되었다는 말임
do_union(root, i); // 연결을 해주어야 함
answer++;
}
}
cout << answer;
return 0;
}