깊이우선탐색(DFS)를 활용하는 전형적인 문제이다. DFS란 Depth First Search의 약자로, 트리나 그래프에서 한 루트로 쭉 최대한 깊숙이 탐색한 다음 더이상 이동할 노드가 없을 경우 다시 돌아와 다른 루트를 탐색하는 기법이다.
알고리즘 구조 상 스택이나 재귀함수를 통해 구현할 수 있지만, 실제 구현 시에는 대부분 재귀함수를 통해 구현하므로 함수 호출 순서만 정확히 짚고 넘어가면 크게 어려울 부분은 없다.
노드 수 V, 에지 수 E라고 하면 시간복잡도는 가 되며 주로 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등의 문제를 풀때 사용한다.
DFS에 대해 설명하는 시간이 아니므로, 이에 대한 자세한 개념은 구글링을 통해 찾아보길 바란다.
(워낙 유명한 알고리즘이기에 친절한 설명이 많다)
문제에서는 연결 요소의 개수를 구하는 프로그램을 구현해달라고 했다. 예제 입력을 그래프로 표현하면 다음과 같다.
노드 간 연결이 1 - 2 - 5 | 3 - 4 - 6으로 구성되어 있으므로 연결 요소는 2개이다.
앞으로 DFS를 통해 문제를 풀때는 무조건 2가지 자료구조를 생각해보는게 좋다.
(반드시 사용하진 않지만 DFS 개념을 복기하고 문제를 이해하는데 많은 도움이 된다.)
- 2차원 인접 리스트
- 1차원 방문 리스트
2차원 인접리스트를 통해 노드 간의 연결관계를 표현한다. 다음은 예제 입력에 대한 인접리스트이다.
1번 노드는 2, 5번 노드로 이동할 수 있으며, 2번 노드는 1, 5번 노드, 3번 노드는 4번 노드... 와 같이 표현한 것이다.
다음은 예제 입력에 대한 방문리스트이다.
초기에는 아무 노드에도 방문하지 않았으므로 모두 False로 셋팅해 놓는다.
이후 DFS 탐색을 통해 한 루트에 대해 탐색을 모두 진행하면 하나의 연결된 요소로 판단하여 카운팅한다.
DFS 탐색을 통해 1 - 2 - 5를 모두 탐색한 경우 아래와 같이 1, 2, 5번 노드에 대해 방문한 표시로 True가 될 것이다.
이 시점에서 카운트를 진행하면 되는 것이다.
Python
따라서 파이썬의 문제풀이 코드는 다음과 같다.
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
N, M = map(int, input().split())
# 인접 리스트로 그래프를 저장할 2차원 리스트
A = [[] for _ in range(N + 1)]
# 방문 여부를 체크하는 리스트
# 모든 노드를 방문하지 않은 상태(False)로 초기화
visited = [False] * (N + 1)
def DFS(v):
visited[v] = True # 방문한 노드를 True로 표시
# 현재 v노드에 연결된 모든 노드를 탐색
for i in A[v]:
# e.g. v = 1, A[1] = [2, 5]라면
# 1번 노드에서 인접한 2번 5번 노드에 대해 재귀함수 호출
if not visited[i]:
DFS(i)
# 간선의 개수만큼 입력받음
for _ in range(M):
# 양 끝점 입력
s, e = map(int, input().split())
# 무방향 그래프이므로 서로 간선을 추가함
A[s].append(e)
A[e].append(s)
# 연결 요소를 카운트할 변수
count = 0
# 모든 정점의 개수인 N만큼 반복
for i in range(1, N + 1):
# 인접 리스트 A에서 방문하지 않은 노드가 있다면
if not visited[i]:
count += 1 # 연결 요소 카운트
DFS(i) # DFS 함수를 통해 연결된 모든 노드 방문 처리
print(count)Java
따라서 자바의 문제풀이 코드는 다음과 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class P_11724 {
static ArrayList<Integer>[] A;
static boolean[] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
A = new ArrayList[N + 1]; // 인접 리스트 배열 인스턴스 생성
visited = new boolean[N + 1]; // 방문 리스트 생성 (자동으로 false 초기화)
// 배열의 각 요소에 대해 ArrayList<Integer> 객체로 인스턴스 생성 -> 인접 리스트 초기화
for (int i = 1; i <= N; i++) {
A[i] = new ArrayList<Integer>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
// 양방향 에지이므로 양쪽에 간선 추가
A[start].add(end);
A[end].add(start);
}
int count = 0;
// 각 노드에 대해 방문 여부 체크
for (int i = 1; i <= N; i++) {
if (!visited[i]) {
count++;
DFS(i); // 아직 방문하지 않았다면 DFS 실행
}
}
System.out.println(count);
}
static void DFS(int v) {
visited[v] = true; // 먼저 방문했다는 의미로 true로 바꿔준 후
// v 노드에 연결되어 있는 모든 노드에 대해 방문 여부 반복
for (int i : A[v]) {
if (!visited[i]) {
DFS(i); // 아직 방문하지 않았다면 DFS 재귀실행
}
}
}
}