Algorithm

DFS

DFS는 그래프 탐색 방법중에서 하나인 깊이우선 탐색입니다.

참고로 여기서 탐색은 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘을 뜻합니다.

그래프 탐색 방법을 배우기전에 그래프의 표현에 대해서 좀 더 알아보고 오면 좋습니다.

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

깊이우선 탐색은 그래프를 전부다 탐색하는 기능을 가지고 있고 다음과 같은 특징이 존재합니다.

1. 재귀함수로 구현이 가능합니다.
2. 스택 자료구조를 이용하여 구현이 가능합니다.

이와 같은 특징을 가지고 시간복잡도는 O(V + E), 여기서 V는 노드수이고 E는 에지수 입니다.

DFS 핵심이론

DFS의 핵심 이론은 한 번 방문한 노드는 다시 방문하면 안됩니다.

그 이유는 사이클을 방지하고, 무한 루프를 피하기 위함 입니다.

이를 위해 DFS 구현시 노드 방문 여부를 체크할 배열이 필수입니다.

또한 DFS는 후입선출 특성을 가지고 있으므로 스택이나 재귀함수를 사용하는데, 주로 스택 성질을 갖는 재귀함수를 많이 사용합니다.

사용법 [ 백준 11724번 문제 ]

여기서는 재귀함수를 이용 했습니다.

import org.w3c.dom.Node;

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

public class 연결_요소의_개수_구하기_11724 {
    static boolean[] visited; // 각 노드의 방문 여부를 저장하는 배열
    static ArrayList<Integer>[] list; // 각 노드의 이웃 노드를 저장하는 인접 리스트
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        int A = Integer.parseInt(st.nextToken()); // 노드의 개수
        int B = Integer.parseInt(st.nextToken()); // 간선의 개수
        list = new ArrayList[A];
        visited = new boolean[A];
        int count = 0; // 연결 요소의 개수를 저장하는 변수
        
        // 각 노드의 이웃 노드를 저장하는 인접 리스트 초기화
        for (int i = 0; i < A; i++) {
            list[i] = new ArrayList<>();
        }

        // 입력된 간선 정보를 인접 리스트에 저장
        for(int i = 0; i < B; i++){
            st = new StringTokenizer(in.readLine());
            int C = Integer.parseInt(st.nextToken());
            int D = Integer.parseInt(st.nextToken());
            list[C-1].add(D); // 노드 C의 이웃 노드에 D 추가
            list[D-1].add(C); // 노드 D의 이웃 노드에 C 추가
        }

        // 모든 노드에 대해 DFS 실행하여 연결 요소 개수 카운트
        for (int z = 0; z < A; z++) {
            if(!visited[z]){ // 해당 노드가 방문되지 않았으면
                DFS(z); // DFS 실행
                count++; // 연결 요소 개수 증가
            }
        }
    }

    // DFS 함수: 재귀적으로 노드를 방문하고 이웃 노드를 탐색
    static void DFS(int z) {
        if (visited[z]) { // 이미 방문한 노드인 경우
            return; // 재귀 종료
        }
        visited[z] = true; // 방문한 노드로 표시

        // 현재 노드의 이웃 노드를 탐색
        for (int i : list[z]) {
            DFS(i-1); // 이웃 노드에 대해 DFS 재귀 호출
        }
    }
}