[알고리즘] DFS(깊이 우선 탐색)

1. 개념

주어진 어떤 정점을 출발하여 체계적으로 그래프의 모든 정점들을 순회하는 것을 그래프 순회라고 한다. DFS는 그래프를 순회하는 방법 중 하나이다. 

DFS는 시작 노드부터 출발해서, 시작 노드와 인접한 것 중 하나를 방문한다. 그리고 그 방문한 것과 인접한 것을 또 방문한다. 이렇듯 시작 노드부터 인접한 것을 따라 계속 그걸 방문해나가는 방법이다. 마치 아래 방향으로 쭉 깊이있게 탐색하는 것 같다. 만약, 더 이상 방문할 것이 없다면 이전 노드로 돌아와서 이전 노드와 인접해 있지만 아직 방문하지 않은 노드를 방문해 나간다.

 

2. 예시

위와 같은 그래프를 DFS로 방문하면 다음과 같다. 같은 단계일 경우 오름차순으로 노드를 방문한다.

1 -> 2 -> 6 -> 8 -> 3 -> 5 -> 4 -> 7 ->

 

3. 특징

• 재귀 함수로 구현할 때는 스택 오버플로우에 유의해야 한다.
• 시간 복잡도는 O(노드수 + 엣지 수)
• 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등의 문제에 적용할 수 있다

 

4. 코드

• 그래프라는 것이 명시적일 경우

// 재귀함수로 구현
import java.io.*;

public class Main {
    static boolean[] visited = new boolean[9];
    static int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
    public static void main(String[] args) throws IOException {
        dfs(1);
    }
    
    static void dfs(int nodeIndex){
        visited[nodeIndex] = true;
        
        System.out.print(nodeIndex + " ->");
        
        for(int node : graph[nodeIndex]){
            if(!visited[node]){
                dfs(node);
            }
        }
    }

}

// 스택으로 구현

import java.io.*;
import java.util.Stack;

public class Main {
    static boolean[] visited = new boolean[9];
    static int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
    static Stack<Integer> stack = new Stack<>();
    
    public static void main(String[] args) throws IOException {
        stack.push(1);
        visited[1] = true;
        
        while(!stack.isEmpty()){
            int nodeIndex = stack.pop();
            System.out.print(nodeIndex + " -> ");
            for(int LinkedNode : graph[nodeIndex]){
                if(!visited[LinkedNode]){
                    stack.push(LinkedNode);
                    visited[LinkedNode] = true;
                }
            }
        }
    }

    

}

• 그래프라는 것이 명시적이지 않을 경우
  • 방문 배열 필요 없으면 안 만들어도 됨
  • 종료조건 잘 명시 후 아래에 재귀적으로 함수 부르기

 

5. 관련 문제

백준 11724

GitHub - Lee-Min-Jung/coding_test_practice

백준 2023

GitHub - Lee-Min-Jung/coding_test_practice

백준 13023

GitHub - Lee-Min-Jung/coding_test_practice

백준 1033

GitHub - Lee-Min-Jung/coding_test_practice

타겟 넘버

여행 경로