백준 11724번. 연결 요소의 개수 (Python / 파이썬)

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

---

문제 풀이

연결 요소의 개수 문제는 방향 없는 그래프가 주어졌을 때, 연결 요소의 개수를 구하는 문제입니다.

연결 요소란 노드들이 서로 연결되어 있느냐를 의미하는 것입니다.

예제 입력 1에서 주어진 그래프를 예로 들어보면,

1, 2, 5번 노드가 서로 연결되어있고 3, 4, 6번 노드가 서로 연결되어 있으므로

연결 요소는 2개라고 할 수 있습니다.

 

저는 이 문제를 다음과 같이 두가지 방법으로 풀이해보았습니다.

 

- 그래프 이론

먼저, 간선으로 연결된 두 노드들을 union 연산을 이용해 합쳐줍니다.

union 연산을 수행해주면 서로 연결된 노드들의 루트 노드는 동일해집니다.

따라서 각 노드들의 루트 노드를 find 연산을 이용해 찾아주고

result 리스트에 삽입해주었습니다.

set 함수는 집합 자료형을 만들어주는 함수입니다.

집합 자료형은 중복을 허용하지 않습니다. 따라서 중복을 제거하는데 사용하기 좋습니다.

set 함수를 이용해 result 리스트를 집합 자료형으로 만들어주면 서로 다른 루트 번호만 남게 됩니다.

따라서 집합 자료형으로 만들어 준 result의 길이를 출력하면 연결 요소의 개수를 출력할 수 있습니다.

 

- BFS 알고리즘

먼저, 간선으로 연결된 두 노드들을 양방향으로 연결시켜줍니다.

각 노드들에 대해 아직 방문하지 않았다면 BFS 알고리즘을 수행해 연결된 노드들을 탐색해줍니다.

연결된 노드 탐색이 끝났다면 연결 요소의 개수를 증가시켜줍니다.

---

My Code 1 - 그래프 이론

import sys
input = sys.stdin.readline

# 루트 노드를 찾는 연산
def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 노드를 합쳐주는 연산
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

n, m = map(int,input().split()) # 노드 개수, 간선 개수
parent = [0] * (n + 1)          # 루트노드 저장할 list

for i in range(1, n + 1):
    parent[i] = i           # 초기 루트노드는 자기자신

for _ in range(m):
    u, v = map(int,input().split())  # 간선으로 연결된 두 노드번호
    union_parent(parent, u, v)       # union 연산으로 합쳐줌

result = []
for i in range(1, n + 1):
    result.append(find_parent(parent, i)) # 각 노드들의 루트노드를 찾아 삽입

print(len(set(result))) # 집합 자료형으로 만들어주어 중복 제거한 뒤 길이를 출력

 

My Code 2 - BFS 알고리즘

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int,input().split()) # 노드 개수, 간선 개수

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v = map(int,input().split()) # 간선으로 연결된 두 노드 번호
    graph[u].append(v)              # 양방향으로 노드 연결해줌
    graph[v].append(u)

visited = [False] * (n + 1) # 방문했음을 표시할 list

def bfs(v):
    q = deque()
    q.append(v)        # 첫 노드 삽입
    visited[v] = True  # 방문했음을 표시
    while q:
        now = q.popleft()    # 큐에서 삭제
        for i in graph[now]: # 삭제된 노드와 연결된 노드들
            if not visited[i]: # 만약 아직 방문 전이라면
                q.append(i)    # 큐에 삽입
                visited[i] = True # 방문했음을 표시

count = 0
for i in range(1, n + 1): # 각 노드들에 대해
    if not visited[i]:    # 아직 방문하지 않았다면
        bfs(i)            # BFS 알고리즘 수행
        count += 1        # 연결 요소 개수 count

print(count)