백준 - 그래프(# 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% 정도 빨랐다.
Author And Source
이 문제에 관하여(백준 - 그래프(# 11724)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@starteon/백준-그래프-11724저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)