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

---

문제 분석

노드의 최대 개수가 1,000이므로 시간 복잡도 N^2이하의 알고리즘을 모두 사용할 수 있다.
문제에서 말한 연결 요소란 에지로 연결된 노드의 집합이며, 한 번의 DFS가 끝날 때까지 탐색한 모든 노드의 집합을 하나의 연결 요소로 판단할 수 있다.

문제를 보고 구현과정을 생각보면, DFS를 이용하여 문제를 풀어야 겠다는 생각을 할 수 있고, 이 과정에서 재귀함수를 이용하여 각 노드별로 방문하였는지 체크하는 과정이 필요하다. 또한 추가로 인접리스트를 사용하여 노드 간의 관계를 표현하면 된다.

---

소스 코드

# 연결 요소의 개수

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

N, M = map(int, input().split())
arr = [[] for _ in range(N + 1)]
check = [False]*(N+1)
Result = 0


def recursion(currentIdx):
    global check
    global arr

    if not check[currentIdx]:
        check[currentIdx] = True

    for value in arr[currentIdx]:
        if not check[value]:
            recursion(value)


for _ in range(M):
    firstNode, secondeNode = map(int, input().split())
    arr[firstNode].append(secondeNode)
    arr[secondeNode].append(firstNode)

for i in range(1, N+1):
    if not check[i]:
        Result += 1
        recursion(i)

print(Result)

---

해당 문제에서는 방향이 없는 그래프이기 때문에 양쪽 방향으로 에지를 저장할 필요가 있다.
따라서 위의 코드에서도 볼 수 있듯이 arr배열에 입력으로 받은 노드의 번호 2개를 모두 고려하여 양쪽에 저장해주는 과정이 포함되어 있다.