[코딩테스트] 연결요소의 개수

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

문제를 먼저 분석해봅시다

문제가 매우 간단합니다. 무방향 그래프가 주어졌을 때 연결요소의 개수를 구하면 됩니다.

이 문제는 다른거 다 필요없고 dfs를 이용하면 문제를 쉽게 해결할 수 있습니다.

일단 코드부터 보겠습니다.

import sys
sys.setrecursionlimit(10000)

def dfs(graph, start, visited):
    visited[start] = True
    
    # 연결된 요소를 탐색
    for v in graph[start]:
        if not visited[v]:
            dfs(graph, v, visited)
        
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)
answer = 0

for _ in range(M):
    first, second = map(int, input().split())
    graph[first].append(second)
    graph[second].append(first)
    
# dfs 탐색 시작
for i in range(1, N + 1):
    if not visited[i]:
        answer += 1
        dfs(graph, i, visited)
        
print(answer)

코드를 분석합시다

일단 graph라는 변수를 인접리스트로 사용합니다. 간선 정보를 입력할 때마다 각 노드마다 인접한 노드를 죄다 graph에다가 붙입니다. 이 때 무방향 그래프라는 조건이 있기 때문에 graph[first]에는 second를, graph[second]에는 first를 붙입니다.

그리고 탐색을 시작하면 되는데, 탐색 가능한 노드를 만나면 dfs를 통해 죄다 방문 처리를 하고 answer를 1 추가시킵니다.

그렇게 되면 한 노드를 탐색하면서 연결된 모든 노드가 visited에 방문처리가 되기 때문에, 한번에 연결된 노드를 탐색하는 효과를 가집니다.

그렇게하면 answer에는 연결요소들의 갯수가 갱신됩니다. 사실 dfs의 기초 문제임