[백준 11724] 연결 요소의 개수

백준 11724

🔍 알고리즘 분류

• dfs

💡 문제 풀이

1. graph에 연결된 정점을 양방향으로 저장
2. 방문 리스트 False로, ans(연결된 요소) = 0 초기화
3. dfs 진행
   1) 현재 정점 방문 처리
   2) 연결된 정점 탐색 후, 방문하지 않았다면 dfs 진행
4. 1번 노드부터 탐색하며 ans + 1

📄 코드

• Python

# 런타임 에러 방지
import sys
sys.setrecursionlimit(100000)

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)] # 연결 정보
visited = [False] * (n + 1) # 방문 여부
ans = 0 # 정답

for _ in range(m):
    u, v = map(int, input().split())
    # 정점 양 방향 연결
    graph[u].append(v)
    graph[v].append(u)

# 깊이 우선 탐색
def dfs(x):
    # 방문 처리
    visited[x] = True

    # 연결된 정점을 아직 방문하지 않았다면 dfs 진행
    for i in graph[x]:
        if not visited[i]:
            dfs(i)

# dfs 진행
for i in range(1, n + 1):
    if not visited[i]:
        # 연결 요소 개수
        ans += 1
        dfs(i)

# 결과 출력    
print(ans)