11724 연결 요소의 개수

실2

계속 그래프 문제에서도 bfs 로만 푸는 문제가 나왔었는데

dfs로 풀어볼 문제가 나왔다.

해당 문제는 약간 유형이 달랐는데, 기존 문제가 평면상에서 x, y 를 이동시키는 문제였다면 이번은 노드와 관련된 그래프 문제였다.

본격적으로 그래프쪽으로 유형이 옮겨가는 느낌이다.

이 문제의 핵심은 각각의 노드가 point 하고 있는 노드를 배열에 담아주는 인접 리스트를 만들어주는 것이다.

이를 통해 모든 노드를 순회하면서 특정 노드가 깊어지는 과정을 거쳐 노드를 방문 처리해주면, 방문 처리해주지 않은 노드는 새로운 연결 요소가 된다.

이를 코드로 표현하면

N, M = map(int, input().split(" "))
graph = [list(map(int, input().split(" "))) for _ in range(M)]
visited = [False] * (N+1)
count = 0
adj = [[] for _ in range(N+1)]

for n, m in graph:
    adj[n].append(m)
    adj[m].append(n)

def solution():
    global count
    for i in range(1, N+1):
        if not visited[i]:
            visited[i] = True
            count += 1
            dfs(i)
    print(count)

def dfs(node):
    for i in adj[node]:
        if not visited[i]:
            visited[i] = True
            dfs(i)
    return

solution()