[백준 파이썬] 11724 연결 요소의 개수

📌문제 출처

솔브닷 3+ 클래스 단계
https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

❓ 문제

 

❗ 풀이

• Union-Find 알고리즘 활용

📗 풀이 코드

import sys
input = sys.stdin.readline

def find(x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parents[x] != x:
        parents[x] = find(parents[x]) # 재귀 함수를 돌며 부모 노드 탐색하고 초기화
    return parents[x] # 부모 노드를 반환해주어야 재귀 함수를 돌며 중간 노드 초기화 가능

def union(a,b):
    a,b = find(a), find(b) # 각자 버전 부모 노드를 최신 버전(현재의 루트 노드)으로 초기화
    if a<b : # a,b는 간선으로 이어져 있기에 결국 같은 노드이므로 작은 값으로 똑같이 맞춰줌
        parents[b] = a
    else :
        parents[a] = b
        
n,m = map(int,input().split()) # 노드 개수, 간선 개수
nodes = range(1,n+1)
parents = [i for i in range(n+1)] # 자기 자신으로 초기 부모 노드를 설정
for _ in range(m):
    a,b = map(int,input().split())
    union(a,b) # 간선으로 이어진 노드를 같은 부모 노드로 초기화

# 이 때 루트 노드는 발견되었지만 parents가 모두 루트 노드로 되어있지는 않음
for node in nodes: # 마지막으로 모든 노드를 루트 노드로 만들어줌
    find(node)
    
print(len(set(parents))-1)

📗 코드 해설

• 트리 구조에서 같은 부모 노드를 가진 노드끼리 그룹짓는 union-find 알고리즘을 활용
• 설명할 노드는 다음과 같다.
  자식 노드 : 모든 개별 노드
  부모 노드 : 자식 노드 상위의 노드(연결된 노드 중 최소값)
  루트 노드 : 모든 노드의 최상단 부모 노드
• 노드 리스트를 설정해두고 각 노드의 부모 노드도 최초 자기 자신으로 설정해둔다.
• 간선의 두 노드가 들어올 때마다 union 함수를 실행해준다.
  이 때 두 노드를 find 함수를 통해 각자 현재의 루트 노드로 설정해주고
  그 크기를 비교해서 하나의 루트 노드로 초기화한다.
  두 노드는 간선으로 연결되어있기에 무조건 같은 루트 노드를 가진다.
• 이 때 find 함수에 들어가는 노드가 루트 노드라면 부모 노드와 자식 노드가 동일하므로 그대로 반환한다.
  그렇지 않으면 부모 노드를 재귀함수를 통해 찾아준다. 이 재귀함수에는 부모 노드가 인자로 들어가서
  부모 노드에 대한 부모 노드, 즉 루트 노드까지 탐색한다.
• 재귀 함수가 루트 노드에 다다르면 재귀 함수를 한 단계씩 빠져나오면서 부모 노드를 업데이트해준다.
  따라서 하나의 루트 노드를 찾으면 재귀 함수의 시작인 노드부터 루트 노드까지의 모든 부모 노드들 또한
  루트 노드로 초기화된다.
• 모든 간선을 확인했음에도 자식 노드 중 일부는 중간에 확인이 안됐을 수 있기에
  최종적으로 모든 노드들을 반복하며 루트 노드로 업데이트 해준다.