[Python 3] BOJ 20955 민서의 응급 수술

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

해당 문제를 바라보면, 뉴런들로 뇌가 이루어져 있고, 뉴런들은 시냅스를 통하여 연결된다. 하지만 뉴런들끼리 연결이 끊어졌고, 끊어진 시냅스들을 다시 연결하여 모두 뉴런들을 연결하려고 한다. 하지만, 뉴런들을 트리 형태로 연결하려고자 한다. 즉, 뉴런들끼리의 사이클이 존재하지 않아야한다. 하지만 여기서 중요한 점은, "연결되지 않은 두 뉴런을 연결하거나, 이미 연결된 두 뉴런의 연결을 끊는다"이다. 이미 연결된 뉴런들, 즉 시냅스들을 사이클이 발생될 경우 끊어내야 한다.

이번 문제는 분리 집합을 이용한 문제였다.

분리 집합을 형성해서, 뉴런들끼리의 연결 관계들을 검토한다. 연결 관계의 두 노드가 이미 같은 부모 뉴런을 가지고 있는 경우, 이 연결은 끊어내야한다. 해당 노드를 연결하게 되면, 사이클이 발생되기 때문이다. 즉, 연산을 실행해야 한다. 만약 다른 부모 뉴런을 가지고 있는 경우, 연결을 실시한다.

모든 연결들에 대한 검토가 끝난 후, 모든 부모 노드들의 개수를 보고, 이들끼리 잇는 연산을 실행한다.

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
parents=[i for i in range(n+1)]
def find(x):
    if parents[x]!=x:
        parents[x]=find(parents[x])
    return parents[x]

answer=0
def merge(x,y):
    global answer
    x=find(x)
    y=find(y)
    if x==y:
        answer+=1
    elif x<=y:
        parents[y]=x
    else:
        parents[x]=y

for _ in range(m):
    u,v=map(int,input().split())
    merge(u,v)
for i in range(1,n+1):
    parents[i]=find(parents[i])
print(answer+len(set(parents[1:]))-1)

먼저, input을 받고 부모 배열을 만든다.
이후, 크루스칼 알고리즘을 이용하여 분리 집합 알고리즘을 사용할 것이기 때문에 union / find 함수를 제작하였다.
merge를 할 때, 이미 연결이 되어 있는 경우, 연산을 +=1하고,
연결이 처음부터 되어있지 않는 경우 연결을 실시한다.

이후 제대로 부모 배열과 매칭이 되었는지, parents[i]= find(parents[i])를 실시한다.
이를 하지 않으면, 자신의 부모배열이 왜곡되었을 수 있기에 이후 group이 연결될때 제대로 처리가 되지 않았을 수도 있다.