[BOJ 11724] 연결요소의 개수

Depth First Search

[BOJ 11724] 연결요소의 개수

문제

구조화

• node의 개수 N, Edge의 개수 M 정의
• 해당 문제는 탐색 순서나, 연결 요소의 여부를 구하는 것이 아닌 연결된 군집의 개수를 구하는 문제
• 아래 그림처럼, 서로 연결된 트리의 개수를 구하는 문제.
• Idea
  • 모든 Node에 대해서 DFS 수행
  • 단 이전 재귀 호출 시 방문한 노드라면 같은 연결 군집 내의 Node이므로 Pass
  • 이후 State에서 변화가 있다면, 즉 다른 연결 군집을 탐색한 경우라면, 연결요소의 기준 가산

예제 시각화

해답

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n,m = map(int, input().split())
graph = [[] for i in range(n+1)]
state = [False for _ in range(n+1)]
for i in range(m):
    a,b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(node):
    state[node]=True
    
    for nxt in graph[node]:
        if state[nxt]==False:
            state[nxt]=True
            dfs(nxt)

count = 0
for i in range(1, n+1):
    if state[i] == False: # Start
        count += 1 # count 증가
        dfs(i) # 재귀 형태로 연결된 모든 노드 방문, 즉 state가 변하지 않는 값의 경우 다음 Loop에서 검출되는 Process
        
print(count)