백준 11724 - 연결 요소의 개수 (Python3)
코드
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for i in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
cnt = 0
visited = [False] * (n+1)
def dfs(graph, v, visited):
visited[v] = True
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
for j in range(1, n+1):
if not visited[j]:
dfs(graph, j, visited)
cnt += 1
print(cnt)
문제 해설
방향이 없는 그래프일 때, ‘연결 요소’의 개수를 구하는 문제이다.
**연결 요소 **
-
하나의 그래프가 겹치는 정점없이 각각의 부분으로 나누어져 있을 때, 그 각각의 부분을 의미
<출처 : 위키피디아>
DFS를 구현 한 후, 각 노드를 시작점으로 하여 노드마다 DFS를 실행해준다.
- 노드와 연결된 노드를 처음 방문하는 경우 방문했다는 것을 체크한다.
- 이어서 더 방문할 노드가 없는 경우, 개수를 1 증가시키고 다음 노드로 넘어간다.
- 1, 2의 과정을 모든 노드에 대하여 반복한다.
댓글남기기