[Python] 11724 - 연결 요소의 개수

 

1. 문제 정의

그래프가 주어졌을 때, 연결 요소 즉 트리의 갯수를 찾는 문제이다.

 

2. 풀이 방식

그래프의 탐색(DFS, BFS)을 이용하여 문제를 해결하였다. 

이전에 풀었던 그래프 탐색 문제를 참고하여 문제를 해결할 수 있었다.

 

1) 깊이 우선 탐색(DFS)

# 11724  연결 요소의 개수 (DFS)

import sys
sys.setrecursionlimit(100000)

input = sys.stdin.readline

N, M = map(int, input().split())

graph = [[] for _ in range(N+1)] # 그래프 초기화
visited = [False] * (N+1) # 방문 여부
count = 0 # 트리 탐색

for _ in range(M):
    a, b = map(int, input().split())
    graph[a] += [b] # a에 b 연결
    graph[b] += [a] # b에 a 연결 -> 양방향

# 깊이 우선 탐색(재귀 함수)
def dfs(start_v, visited):
    visited[start_v] = True

    for nx in graph[start_v]:
        if not (visited[nx]):
            dfs(nx, visited)

    return 1 # 트리 탐색을 마치면 1을 반환

for i in range(1, N+1):
    if not (visited[i]):
        count += dfs(i, visited)

print(count)

 

2) 넓이 우선 탐색(BFS)

# 11724  연결 요소의 개수 (BFS)

from collections import deque
import sys

input = sys.stdin.readline

N, M = map(int, input().split())

graph = [[] for _ in range(N+1)] # 그래프 초기화
visited = [False] * (N+1) # 방문 여부
count = 0 # 트리 탐색

for _ in range(M):
    a, b = map(int, input().split())
    graph[a] += [b] # a에 b 연결
    graph[b] += [a] # b에 a 연결 -> 양방향

# 넓이 우선 탐색
def bfs(start_v, visited):
    Q = deque([start_v])

    while Q:
        c = Q.popleft()

        for nx in graph[c]:
            if not (visited[nx]):
                visited[nx] = True
                Q.append(nx)

    return 1 # 트리 탐색을 마치면 1을 반환

for i in range(1, N+1):
    if not (visited[i]):
        count += bfs(i, visited)

print(count)

 

3. 후기

그래프 탐색 문제에 어느정도 개념이 잡힌 것 같다. BFS, DFS 둘 다 필요에 따라 사용할 수 있도록 최대한 두 가지 방법 모두를 활용하여 문제를 해결하려고 노력하고 있다.