[알고리즘] DFS 깊이 우선 탐색 알아보기 ( 백준 2667번 단지번호 붙이기 with 자바)

 

🤔 DFS ( Depth First Search ) 깊이 우선 탐색?

 

그래프 탐색 알고리즘으로 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 알고리즘 입니다.

즉 그래프 형태의 자료구조에서 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다.

그림처럼 한 방향으로 인접한 노드가 없을 때까지 탐색한 후 이전 노드로 돌아가서 다음 인접한 노드를 탐색하며 이 과정을 반복합니다.

 

장점

• 현재 경로상의 노드를 기억하기 때문에 적은 메모리를 사용합니다.
• 찾으려는 노드가 깊은 단계에 있는 경우 BFS보다 빠르게 찾을 수 있습니다.

단점

• DFS를 통해 얻어진 해가 최단 경로라는 보장이 없습니다. DFS는 찾으려는 해에 도착하면 탐색을 종료하기 때문입니다.
• 최악의 경우, 가능한 모든 경로를 탐색함으로 해에 도달하는 데 가장 오랜 시간이 걸릴 수 있다.

 

✔ 문제 유형

• 경로탐색 유형 ( 최단거리, 시간 )
• 네트워크 유형 ( 연결 )
• 조합 유형 (모든 조합 만들기 )

 

✔ 시간 복잡도

DFS를 사용할 때 그래프를 인접 행렬 또는 인접 리스트 로 표현할 경우에 달라집니다.

출처 : https://howtolivelikehuman.tistory.com/75

 

인접 행렬은 이차원 배열을 사용하기 때문에 그래프의 Vertex의 수 만큼 이차원 배열을 생성합니다.

DFS의 특성상 해가 정해져있지 않으면 모든 노드를 탐색해야 합니다.

이차원 배열의 모든 방을 탐색한다면 Vertex * Vertex 즉, O( N^2)의 시간복잡도를 가지게 됩니다

 

인접 리스트는 LinkedList를 사용하기 때문에 각 Vertex(노드)에서 연결선(Edge)으로 연결된 Vertex까지 탐색하며 각 Vertex와 Edge의 수만큼 탐색하게 됩니다. 즉, Vertex + Edge를 더한 만큼 O( Vertex + Edge )의 시간복잡도를 가지게 됩니다.

 

✔ 탐색 방법

탐색은 Stack 또는 재귀함수를 사용하여 구현할 수 있습니다.

백준 2667번을 예제로 DFS를 사용해 보겠습니다.

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

2667번: 단지번호붙이기

백준 2667 문제

 

그림처럼 행렬에서 인접한 집( 1 )의 수와 각 집이 모여있는 단지의 수를 찾는 문제입니다.

🔎 재귀함수 사용

조건에 맞는 인접한 노드를 다시 함수를 호출하여 탐색합니다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.lang.StringBuilder;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

public class Main{

	static List<Integer> result;
    static boolean[][] chk;
    static int[][] map;
    static int cnt, n;
    
	public static void main(String[] args) throws IOException {
       	BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
        
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        chk = new boolean[n][n];
        result = new ArrayList<>();
        cnt = 1;

		// 입력받은 지도(행열)를 탐색하기위해 이차원배열에 추가해줍니다.
        for( int i = 0; i<n; i++){
            String[] arr = br.readLine().split("");
            for( int j = 0; j<n; j++){
                map[i][j] = Integer.parseInt(arr[j]);
            }
        }

        for( int i = 0; i<n; i++){
            for( int j = 0; j<n; j++){
                if( map[i][j] == 1 && !chk[i][j] ){ // 1이고 체크하지 않은 즉, 탐색하지 않은 집
                    dfs(i, j); // dfs 호출
                    result.add(cnt); // dfs를 통해 인접한 집 수 추가
                    cnt = 1; // cnt 초기화
                }
            }
        }    
        
        Collections.sort(result); // 오름차순 정렬
        sb.append(result.size()).append("\n");
        for( int i : result ){
            sb.append(i).append("\n");
        }
        
        System.out.print(sb);
	}
    
    static void dfs(int y, int x){
        chk[y][x] = true;
        int[] dy = {0,1,0,-1};
        int[] dx = {1,0,-1,0};
        for( int i = 0; i<4; i++){ // 4방향의 노드를 모두 탐색
            int ny = y + dy[i];
            int nx = x + dx[i];
            if( ny >= 0 && nx >= 0 && ny < n && nx < n ){ //인접한 노드가 없다면 탐색하지 않습니다.
                if( map[ny][nx] == 1 && chk[ny][nx] == false){
                    cnt++;
                    dfs(ny, nx); // dfs재귀 호출
                }
            }
        }
    }
    
}

 

🔎 Stack 사용

 조건에 맞는 인접한 노드들을 stack에 모두 담고 하나씩 제거하면서 탐색을 수행합니다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.lang.StringBuilder;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;

public class Main{

	static List<Integer> result;
    static boolean[][] chk;
    static int[][] map;
    static int cnt, n;
    static Stack<int[]> stack;
    
	public static void main(String[] args) throws IOException {
       	BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
        
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        chk = new boolean[n][n];
        result = new ArrayList<>();
        stack = new Stack<>();
        cnt = 1;

		// 입력받은 지도(행열)를 탐색하기위해 이차원배열에 추가해줍니다.
        for( int i = 0; i<n; i++){
            String[] arr = br.readLine().split("");
            for( int j = 0; j<n; j++){
                map[i][j] = Integer.parseInt(arr[j]);
            }
        }

        for( int i = 0; i<n; i++){
            for( int j = 0; j<n; j++){
                if( map[i][j] == 1 && !chk[i][j]){
                    dfsUseStack(i, j);
                    result.add(cnt);
                    cnt=1;
                }
            }
        }   
        
        Collections.sort(result); // 오름차순 정렬
        sb.append(result.size()).append("\n");
        for( int i : result ){
            sb.append(i).append("\n");
        }
        
        System.out.print(sb);
	}
    
    static void dfsUseStack(int y, int x){
        chk[y][x] = true;
        stack.push(new int[]{y, x});
        int[] dy = {0,1,0,-1};
        int[] dx = {1,0,-1,0};

        while (!stack.isEmpty()){
            int[] arr = stack.pop();
            for( int i = 0; i<4; i++){
                int ny = arr[0] + dy[i];
                int nx = arr[1] + dx[i];
                if( ny >= 0 && nx >= 0 && ny < n && nx < n ){ //하지만 옆 노드가 없다면 탐색하지 않도록 조건
                    if( map[ny][nx] == 1 && chk[ny][nx] == false){
                        cnt++;
                        chk[ny][nx] = true;
                        stack.push(new int[]{ny, nx}); //조건에 맞는 인접노드를 stack에 추가합니다.
                    }
                }
            }
        }

    }
    
}

 

---

 

📚 Reference :

https://howtolivelikehuman.tistory.com/75

https://velog.io/@sukong/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%9C%EB%85%90-%EA%B9%8A%EC%9D%B4%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89DFS