[ Java ] 백준 11724번 연결 요소의 개수 (+DFS 이론 정리)

DFS(깊이 우선 탐색)

깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나이다.

깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다. 

기능	특징	시간 복잡도 (노드 수:V , 에지 수 :E)
그래프 완전 탐색	- 재귀 함수로 표현 - 스택 자료구조 이용	O(V+E)

 

깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로에 유의해야 한다.

깊이 우선 탐색의 핵심 이론

• DFS는 한 번 방문한 노드를 다시 방문하면 안되므로, 노드 방문 여부를 체크할 배열이 필요
• 그래프는 인접 리스트로 표현한다.
• DFS의 탐색 방식은 후입선출 특성을 가진다. (스택 사용)
• DFS 구현은 스택보다는 스택 성질을 갖는 재귀 함수로 많이 구현한다.

DFS를 시작한 노드를 정한 후 사용할 자료구조 초기화하기

DFS를 위해 필요한 초기 작업

• 인접 리스트로 그래프 표현하기
• 방문 배열 초기화하기
• 시작 노드 스택에 삽입하기

스택에 시작 노드를 1로 삽입할 때 해당 위치의 방문 배열을 체크하면 T,F,F,F,F,F 가 된다.

스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기

pop을 수행하여 노드를 꺼낸다.

꺼낸 노드를 탐색 순서에 기입하고 인접 리스트의 인접 노드를 스택에 삽입하며 방문 배열을 체크한다.

방문 배열은 T,T,T,F,F,F가 된다.

스택 자료구조에 값이 없을 때까지 반복하기

앞선 과정을 스택 자료구조에 값이 없을 때까지(더 이상 갈 수 있는 곳이 없을 때까지) 반복한다.

이때 이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는 것이 핵심이다.

스택에 노드를 삽입할 때 방문 배열을 체크하고, 스택에서 노드를 뺄 때 탐색 순서에 기록하며 인접 노드를 방문 배열과 대조하여 살펴본다.

 

연결 요소의 개수 #11724

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

11724번: 연결 요소의 개수

문제 분석하기

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

손으로 풀어보기 

① 그래프를 인접 리스트로 저장하고 방문 배열도 초기화한다. 방향이 없는 그래프이므로 양쪽 방향으로 에지를 모두 저장한다.

② 임의의 시작에서 DFS를 수행한다. 현재의 경우 1을 시작점으로 정하였고, 탐색을 마친 이후 방문한 곳은 1,2,5가 되었다.

③. 아직 방문하지 않은 노드가 있으므로 시작점을 다시 정해 탐색을 진행한다. 현재의 경우 3,4,6 순서로 탐색을 마쳤다. 모든 노드를 방문했으니 전체 탐색을 종료한다. 

 ④. ①~③ 과정을 통해 총 2번의 DFS가 진행되었다는 것을 알 수 있다. 즉, 연결 요소 개수는 2개이다.

 

슈도 코드 작성하기

n(노드 개수) m(에지 개수)
A(그래프 데이터 저장 인접 리스트)
visited(방문 기록 저장 배열)
for(n의 개수만큼 반복하기){
    A 인접 리스트의 각 ArrayList 초기화하기
}
for(m의 개수만큼 반복하기){
    if(방문하지 않은 노드가 있으면){
        연결 요소 개수 ++
        DFS 실행하기
    }
}

// DFS 구현하기
DFS{
    if(현재 노드 == 방문노드) return;
    visited 배열에 현재 노드 방문 기록하기
    현재 노드의 연결 노드 중 방문하지 않은 노드로 DFS 실행하기(재귀 함수 형태)
}

 

정답코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static boolean visited[];
    static ArrayList<Integer>[] A;

    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());
        visited = new boolean[n + 1];
        A = new ArrayList[n + 1];

        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 s = Integer.parseInt(st.nextToken()); // 시작점
            int e = Integer.parseInt(st.nextToken()); // 종료점
            A[s].add(e);
            A[e].add(s);
        }

        int count = 0;

        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                count++;
                DFS(i);
            }
        }

        System.out.println(count);
    }

    private static void DFS(int v) {
        if (visited[v]) return;
        visited[v] = true;
        for (int i : A[v]) {
            if (!visited[i]) {
                DFS(i);
            }
        }
    }
}