백준 - 그래프(# 11724)

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

Code 1

import sys

# make adjacent list (graph)
n, m = map(int, input().split())
comp_num = 0
adj_list = {i:[] for i in range(1,n+1)}
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    adj_list[a].append(b)
    adj_list[b].append(a)

# dfs & find the number of component
visited = {}
for start_v in range(1,n+1):
    if start_v not in visited:
        stack = [start_v]
        while stack:
            v = stack.pop()
            if v not in visited:
                visited.setdefault(v)
                stack += adj_list[v]
        comp_num += 1

print(comp_num)

Code 2

### using recursion for dfs ###
import sys

sys.setrecursionlimit(10000)
def dfs(v):
    visited.setdefault(v)   
    for i in adj_list[v]:
        if i not in visited :
            dfs(i)

# make adjacent list (graph)
n, m = map(int, input().split())
comp_num = 0
adj_list = {i:[] for i in range(1,n+1)}
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    adj_list[a].append(b)
    adj_list[b].append(a)
            
# dfs & find the number of component
visited = {}
for start_v in range(1,n+1):
    if start_v not in visited:
        dfs(start_v)
        comp_num += 1

print(comp_num)

참고

dfs를 이용하여 그래프를 순회하며 component의 개수를 셌다. dfs 알고리즘 한 번에 요소 한 개이다. Code 1 은 Stack을 이용하여 dfs를 구현하였고, Code 2 는 재귀함수로 구현하였다. 거의 비슷한 성능을 보였지만, 재귀함수로 구현한 것이 ~10% 정도 빨랐다.