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

 

 

 

DFS(Depth-First Search) 알고리즘은 깊이 우선 탐색 방법으로, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

 

 

 

 

DFS는 스택 자료구조 혹은 재귀 함수를 주로 이용하며 모든 노드를 탐색한다.

 

 

 

 

 

 

예시를 살펴보자

 

 

그래프 예시

 

위와 같은 그래프가 있다.

 

 

시작 노드는 1이며, 방문 기준은 번호가 낮은 인접 노드라고 가정하자.

 

 

 

 

 

 

1

 

 

시작 노드 1에서 인접한 노드는 '2', '3', '8' 이다.

 

우리는 방문 조건에 따라 번호가 작은 2번 노드에 방문할 것이다.

 

 

이 때 스택에 1 - 2 를 차례로 담아준다.

 

 

 

 

 

2

 

 

 

노드 2에서 방문하지 않은 인접 노드 '7'에 방문해준다.

 

 

이 때 스택은 1 - 2 - 7 이 된다.

 

 

 

 

 

3

 

 

노드 7의 인접 노드 '6', '8' 중 작은 번호인 노드 6에 방문한다.

 

 

이 때 스택은 1 - 2 - 7 - 6 이 된다.

 

 

 

 

 

4

 

 

 

노드 6에서 방문하지 않은 인접 노드가 존재하지 않으므로 스택에서 노드 6을 꺼내준다. (pop)

 

 

따라서 스택에는 1 - 2 - 7 이 담겨있다.

 

 

 

 

 

 

5

 

 

 

스택의 최상단 노드인 7에서 갈 수 있는 인접한 노드 '8'을 스택에 추가한다.

 

 

스택에는 1 - 2 - 7 - 8 이 담기게 된다.

 

 

 

 

---

 

 

이런 식으로 DFS를 진행하다 보면 전체 노드의 탐색 순서는 1 - 2 - 7 - 6 - 8 - 3 - 4 - 5 가 된다.

 

 

 

 

이를 자바 코드로 살펴보자.

 

import java.util.*;

public class DFS {

    public static boolean[] visited = new boolean[9];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

    // DFS 함수 정의
    public static void dfs(int x) {
        // 현재 노드를 방문 처리
        visited[x] = true;
        System.out.print(x + " ");
        // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        for (int i = 0; i < graph.get(x).size(); i++) {
            int y = graph.get(x).get(i);
            if (!visited[y]) dfs(y);
        }
    }

    public static void main(String[] args) {
        // 그래프 초기화
        for (int i = 0; i < 9; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // 노드 1에 연결된 노드 정보 저장 
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(1).add(8);
        
        // 노드 2에 연결된 노드 정보 저장 
        graph.get(2).add(1);
        graph.get(2).add(7);
        
        // 노드 3에 연결된 노드 정보 저장 
        graph.get(3).add(1);
        graph.get(3).add(4);
        graph.get(3).add(5);
        
        // 노드 4에 연결된 노드 정보 저장 
        graph.get(4).add(3);
        graph.get(4).add(5);
        
        // 노드 5에 연결된 노드 정보 저장 
        graph.get(5).add(3);
        graph.get(5).add(4);
        
        // 노드 6에 연결된 노드 정보 저장 
        graph.get(6).add(7);
        
        // 노드 7에 연결된 노드 정보 저장 
        graph.get(7).add(2);
        graph.get(7).add(6);
        graph.get(7).add(8);
        
        // 노드 8에 연결된 노드 정보 저장 
        graph.get(8).add(1);
        graph.get(8).add(7);

        dfs(1);
    }
}

 

 

2중 ArrayList를 이용하여 2차원 배열처럼 사용할 수 있다.

 

 

여기에 각 노드별로 연결되어 있는 노드 번호를 직접 저장한다.

 

 

방문한 노드는 visit[] 배열에서 배열 값이 false일 때만 재귀하며 true로 변경해주고 노드의 순서를 알기 위해 print 한다.

 

 

 

 

결과

 

 

코드 결과값을 통해 DFS를 이용한 노드 탐색 순서를 한눈에 볼 수 있다.

 

 

 

 

 

 

---

 

 

DFS의 예시로 음료수 얼려먹기 문제를 살펴보도록 하자.

 

 

 

문제

 

 

 

 

 

위의 문제는 한 지점에서 상,하,좌,우로 인접한 노드를 살펴보는 방식을 사용할 수 있다.

 

 

예를 들어

 

 

예시

 

 

 

(0,0) 지점에서 시작한다고 가정했을 때 상,하,좌,우 중에서 갈 수 있는 곳을 탐색한다.

 

 

그리고 재귀를 통해 옮겨간 노드에서 상,하,좌,우 중에서 갈 수 있는 곳을 탐색하는 방식을 반복한다.

 

 

더이상 갈 수 없다면 +1을 반환해주면 된다.

 

 

 

 

 

 

코드를 살펴보자

 

import java.util.*;

public class freezing {

    public static int n, m;
    public static int[][] graph = new int[1000][1000];

    // DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
    public static boolean dfs(int x, int y) {
        // 주어진 범위를 벗어나는 경우에는 즉시 종료
        if (x <= -1 || x >=n || y <= -1 || y >= m) {
            return false;
        }
        // 현재 노드를 아직 방문하지 않았다면
        if (graph[x][y] == 0) {
            // 해당 노드 방문 처리
            graph[x][y] = 1;
            // 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
            dfs(x - 1, y);
            dfs(x, y - 1);
            dfs(x + 1, y);
            dfs(x, y + 1);
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // N, M을 공백을 기준으로 구분하여 입력 받기
        n = sc.nextInt();
        m = sc.nextInt();
        sc.nextLine(); // 버퍼 지우기

        // 2차원 리스트의 맵 정보 입력 받기
        for (int i = 0; i < n; i++) {
            String str = sc.nextLine();
            for (int j = 0; j < m; j++) {
                graph[i][j] = str.charAt(j) - '0';
            }
        }

        // 모든 노드(위치)에 대하여 음료수 채우기
        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 현재 위치에서 DFS 수행
                if (dfs(i, j)) {
                	System.out.println("X : " + i + ", Y : " + j);
                    result += 1;
                }
            }
        }
        System.out.println(result); // 정답 출력 
    }
}

 

 

 

방문하지 않은 값인 0이라면 1로 바꿔주고 상, 하 , 좌, 우를 살펴본 후 재귀에 넣어

 

다시 인접 노드 값을 1로 변경하는 방식을 반복한다.

 

 

 

 

결과

 

 

 

처음으로 살펴볼 노드의 x, y값을 출력하여 살펴보았다.

 

 

 

 

 

 

 

 

출처 : 이것이 취업을 위한 코딩테스트다 - https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3