BOJ 20955)민서의 응급수술

문제

민서는 끊어진 시냅스를 복구하는 대신 뇌 속의 모든 뉴런을 하나의 트리 형태로 연결해보고자 한다. 여기서 트리란 사이클이 존재하지 않는 연결 그래프를 의미한다.

민서는 손기술이 뛰어나기 때문에 다음과 같은 연산을 무한히 수행할 수 있다. 연결되지 않은 두 뉴런을 연결하거나 이미 연결된 두 뉴런의 연결을 끊는다.

뉴런의 연결 정보가 주어졌을 때, 모든 뉴런을 하나의 트리 형태로 연결하기 위하여 필요한 최소 연산 횟수를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 뉴런의 개수 N과 시냅스의 개수 M이 주어진다.

이후 M개의 줄에 걸쳐 시냅스로 연결된 두 뉴런의 번호 u, v가 주어진다.

모든 입력은 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 모든 뉴런을 트리 형태로 연결하기 위하여 필요한 최소 연산 횟수를 출력한다.

제한

2 ≤ N ≤ 100,000
1 ≤ M ≤ min(N × (N – 1) / 2, 100,000)
1 ≤ u, v ≤ N
u ≠ v
두 뉴런 사이에는 최대 1개의 시냅스만 존재한다.

---

풀이

시냅스 연결은 트리 형태로 만들어져야 한다. 가능한 연산은 2가지이다.

1. 뉴런 간 링크를 만든다.
2. 뉴런 간 링크를 끊는다.

연산의 횟수는 연산이 적용될 간선의 개수를 헤아리는 것으로 알 수 있다.

1. 뉴런 간 링크를 만드는 경우
   뉴런 간 링크를 최소한으로 만들기 위한 방법은 전체 공간에서 그래프의 개수를 세는 것이다. 이미 연결된 그래프를 끊을 필요 없이 각 그래프에서 하나의 노드끼리만 연결하면 된다. 결과적으로 트리만 만들어지면 되므로 연결 순서는 고려할 필요가 없다.

2. 뉴런 간 링크를 끊는 경우
   뉴런간의 링크를 끊어야 하는 경우는 그래프가 사이클을 포함하고 있는 경우이다. 그래프를 Spanning tree로 만드는 가장 간단한 방법은 순회를 이용하는 것이다. 이미 방문한 노드로 연결된 링크를 제거하면 모든 노드를 한 번만 방문하는 경로를 찾을 수 있다.

알고리즘은 다음과 같다.

cutting = 끊기 연산 횟수
linking = 연결 연산 횟수

1. 1번부터 n번 노드까지 반복한다.
2. 만약 노드를 방문한 적 없다면 linking에 1을 더하고 이 노드를 시작으로 순회한다.
3. 순회하면서 방문한 노드들에 방문사실을 표시한다.
4. 어떤 노드가 방문한 노드라면 방문하지 않는다.
   4.1. 이 노드가 조상 노드라면 cutting에 1을 더한다.
5. 반복이 끝났다면 (linking-1) + cutting을 출력한다.

---

이 문제에서 중요한 점은 주어지는 데이터에 사이클이 포함된다는 것을 인지하는 것이다.

나는 알고리즘 분류에서 트리 분류 중 선택했기 때문에 당연히 입력으로 트리가 들어올 것이라 예상했지만, 문제에선 그런 언급을 하지 않았다. 되려 링크를 끊는 연산이 필요하다는 것으로 사이클이 존재한다는 것을 암시했다.

이 다음 올릴 회사문화 문제에서도 마찬가지로 문제 이해의 중요성이 부각된다.

---

다음은 구현한 프로그램이다.
Python3나 pypy3에서 Recursion error가 발생하지 않기 위해선 재귀 스택의 크기를 확장해야한다. BOJ 서버에서 최대 재귀 깊이는 1000으로 설정되어 있다. 해결방법은 재귀를 사용하지 않거나 sys.setrecursionlimit() 함수로 최대 재귀 깊이를 늘리는 것이다. 100만 정도를 입력하면 재귀 오류가 발생할 확률을 낮출 수 있다.

import sys
limit_number = 100000
sys.setrecursionlimit(limit_number)

def dfs(tree, visited, anccesters, parent, root) :
    visited.add(root)
    cutting_cnt = 0
    anccesters.add(root)
    for i in range(len(tree[root])) :
        if tree[root][i] not in visited :
            cutting_cnt += dfs(tree=tree, visited=visited, anccesters=anccesters, parent=root, root=tree[root][i])
        elif tree[root][i] != parent and tree[root][i] in anccesters:
            cutting_cnt += 1
    anccesters.remove(root)
    return cutting_cnt

def solve() :
    N, M = map(int, sys.stdin.readline().split())
    tree = [[] for _ in range(N+1)]
    num_of_trees = 0
    
    for _ in range(M) :
        A, B = map(int, sys.stdin.readline().split())
        tree[A].append(B)
        tree[B].append(A)
    
    visited = set()
    cutting_cnt = 0
    for i in range(1, N+1) :
        if i not in visited :
            anccesters = set()
            num_of_trees += 1
            cutting_cnt += dfs(tree=tree,visited=visited, anccesters= anccesters, parent=0, root=i)
    
    print((num_of_trees - 1) + cutting_cnt)

solve()