[백준]_11724번 : 연결 요소의 개수(파이썬)

11724번: 연결 요소의 개수

 

무방향 그래프에서 연결 요소의 개수를 세야 하는 문제이다. 조금 더 쉽게 말하자면 간선으로 이어진 묶음이 몇 개 발생하는지 알아내야 한다. 일단 예시 입력 1에 의하면 그래프의 생김새는 아래와 같을 것이다.

묶음이 2개 발생하므로 답은 2

이 문제는 두 가지 방식으로 풀 수 있는데,

 

1. Union-Find 알고리즘

 

해당 알고리즘을 이용하면 모든 노드의 최상위 노드를 모두 찾을 수 있다. 무방향 그래프라 상위 노드 개념은 없지만 유니온 파인드에서는 번호가 가장 작은 노드를 최상위 노드로 명명하고 나머지 노드는 전부 최상위 노드로 값을 바꾼다.

 

즉 1~6까지 존재했던 번호가 1과 3 두 개만 남았기 때문에 남은 번호의 종류가 연결 요소의 개수와 일치하게 된다.

 

최종 코드>>

import sys
from collections import Counter

input = sys.stdin.readline
n, m = map(int, input().split())
parent = [*range(n)]

def find(x):
    if x != parent[x]:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    a = find(a)
    b = find(b)
    if a > b:
        parent[a] = b
    else:
        parent[b] = a

for _ in range(m):
    a, b = map(int, input().split())
    if find(a - 1) != find(b - 1):
        union(a - 1, b - 1)
parent = [find(x) for x in parent] # 경로 압축
ans = Counter(parent)
print(len(ans))

 

#경로 압축(예시 입력 2의 경우가 이러한 현상을 야기한다)

이미 유니온 파인드로 최상위 노드를 찾아주었을 터인데 한 번 더 시행하는 이유가 뭘까? 유니온 파인드는 무방향 그래프를 유방향 그래프로 만들지만 그 대신 한쪽으로만 자식이 몰려 있는 편중 현상을 자동으로 잡아주지 못한다. 그래서 마지막에 해주는 작업이 경로 압축이다. 하지만 진짜 이 과정 한 번만으로 경로가 완전히 압축되었다는 보장이 있을까?

 

애초에 편중 현상이 발생한 이유는 정보의 부족에 있다. 

예시 입력 2의 그래프

경로 압축을 하지 않으면 parent는 다음과 같다.

[0, 0, 0, 0, 0, 2]
# 우리가 원하는 배열 -> [0, 0, 0, 0, 0, 0]

 

 

6번째 노드에서 정보 부족이 발생하여 상위 노드가 2까지 밖에 기록되지 못하였다. 정보 부족이 발생하는 이유는 현재의 노드 연결 정보가 미래에 영향을 미치지 못하기 때문이다.

 

그럼에도 불구하고 한 번만 더 find를 해주면 압축이 완료된다. 왜냐하면 find 한 번만으로 깊이의 끝(최상위 노드)까지 갈  때문이다.

 

2. 너비 우선 탐색(BFS)

 

해당 노드와 연결 되어 있는 모든 노드를 저장해 놓은 그래프를 리스트로 만든다. 이후 모든 노드를 차례대로 방문하면서 기존에 방문하지 않은 노드에 한해서 연결 요소 개수를 1 증가시킨다. 방문 기록은 visited 리스트를 이용하면 된다.

최종 코드>>

import sys
input = sys.stdin.readline

n, line = map(int, input().split())
graph = [[] for _ in range(n + 1)]

for _ in range(line):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [False] * (n + 1)

component_count = 0

for i in range(1, n + 1):
    if not visited[i]:
        component_count += 1
        stack = [i]

        while stack:
            node = stack.pop()
            if not visited[node]:
                visited[node] = True
                stack.extend(neighbor for neighbor in graph[node] if not visited[neighbor])

print(component_count)