[알고리즘] DFS / BFS (깊이 탐색 / 너비 탐색)

그래프 탐색에서 각 정점을 지나가는 과정을 말하고 주로 사용되는 탐색 방법으로는 깊이 우선 탐색(Depth-First Search)과 너비 우선 탐색(Breadth-First Search) 2가지 알고리즘이 있다.

깊이 우선 탐색 (Depth-First Search)

일반적으로 스택과 재귀함수로 구현을 하고 재귀함수가 편하고 많이 사용되고 있다.

탐색 과정

하나의 점에서 한쪽 방향(연결 노드)으로 먼저 이동을 하고 갈 수 있는 끝 점까지 탐색을 한 뒤 다시 시작 지점으로 돌아와 다른 방향으로 끝 점까지 탐색을 시도한다.

진행 중 여러 방향으로 연결된 점이 있다면 시작 점과 같이 한쪽 방향씩 끝 점을 탐색하고 시작 점으로 돌아와 결과를 출력한다.

경로 탐색

깊이 탐색에서 경로 탐색에 경우에는 갈림길이 있을 경우 때문에 우선순위 큐를 활용해서 재귀함수를 사용할 수 있다.

하지만 최적 경로의 경우에는 성능적으로 너비 탐색에 적합하여 깊이 탐색으로는 잘 풀지 않는다.

public class DepthFirstSearch {
    public static void main(String[] args) {
        int[][] map = {
                {1, 1, 1, 1},
                {1, 0, 0, 0},
                {1, 1, 1, 1},
                {1, 0, 0, 1}};

        int cnt = 0;
        Queue<Integer> queue = new PriorityQueue<>();
        queue = dfs(queue, map, 0, 0, 1);
        if (!queue.isEmpty()) cnt = queue.peek();
        System.out.println(cnt);
    }

    private static Queue<Integer> dfs(Queue<Integer> queue, int[][] maps, int x, int y, int cnt) {
        if (!queue.isEmpty() && queue.peek() < cnt) return queue;
        if (x == maps.length-1 && y == maps[0].length-1) {
            queue.offer(cnt);
            return queue;
        }
        if (x >= 0 && y >= 0 && maps.length > x && maps[0].length > y && maps[x][y] != 0) {
            maps[x][y] = 0;

            dfs(queue, maps, x, y + 1, cnt + 1);
            dfs(queue, maps, x + 1, y, cnt + 1);
            dfs(queue, maps, x, y - 1, cnt + 1);
            dfs(queue, maps, x - 1, y, cnt + 1);

            maps[x][y] = 1;

            return queue;
        }
        return queue;
    }
}

범위 탐색 

연결되어 있는 모든 지점들을 하나씩 헤아려 

public class DepthFirstSearch {
    public static void main(String[] args) {
        int[][] map = {
                {1, 1, 1, 1},
                {1, 0, 0, 0},
                {1, 1, 1, 1},
                {1, 0, 0, 1}};

        int cnt = 0;
        cnt = dfs(0, 0, map);
        System.out.println(cnt);
    }

    private static int dfs(int x, int y, int[][] map) {
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        int cnt = 1;
        map[x][y] = 0;
        for (int i = 0; i < dx.length; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];

            if (nextX >= 0 && nextY >= 0 && nextX < map.length && nextY < map[0].length && map[nextX][nextY] == 1) {
                cnt += dfs(nextX, nextY, map);
            }
        }
        return cnt;
    }
}

너비 우선 탐색(Breadth-Firsh Search)

일반적으로 큐를 이용해서 반복하는 구조로 구현을 하고 최단 경로를 찾는 다익스트라 알고리즘 등에 자주 사용된다.

탐색 과정

시작 점에서 움직일 수 있는 방향으로 모두 이동하고 해당 점들에서 다시 움직일 수 있는 방향으로 점차 움직인다.

한 점씩 이동을 하면서 갈 수 있는 끝 점까지 이동을 한 뒤 결과를 출력한다.

경로 탐색

최단 경로 탐색에 경우 여러 가지로 변형하여 너비 탐색 알고리즘이 주로 사용된다.

public class BreadthFirstSearch {
    public static void main(String[] args) {
        int[][] map = {
                {1, 1, 1, 1},
                {1, 0, 0, 0},
                {1, 1, 1, 1},
                {1, 0, 0, 1}};

        int cnt = 0;
        cnt = bfs(0, 0, map);
        System.out.println(cnt);
    }

    private static int bfs(int x, int y, int[][] map) {
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y, 1});
        int[] cur = null;
        while (!queue.isEmpty()) {
            cur = queue.poll();

            for (int i = 0; i < dx.length; i++) {
                int nextX = cur[0] + dx[i];
                int nextY = cur[1] + dy[i];

                if (nextX >= 0 && nextY >= 0 && nextX < map.length && nextY < map[0].length && map[nextX][nextY] == 1) {
                    map[nextX][nextY] = 0;
                    queue.offer(new int[]{nextX, nextY, cur[2] + 1});
                }
            }
        }

        return cur[2];
    }
}

범위 탐색 

public class BreadthFirstSearch {
    public static void main(String[] args) {
        int[][] map = {
                {1, 1, 1, 1},
                {1, 0, 0, 0},
                {1, 1, 1, 1},
                {1, 0, 0, 1}};

        int cnt = 0;
        cnt = bfs(0, 0, map);
        System.out.println(cnt);
    }

    private static int bfs(int x, int y, int[][] map) {
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        map[x][y] = 0;
        int cnt = 0;
        while (!queue.isEmpty()) {
            cnt++;
            int[] cur = queue.poll();

            for (int i = 0; i < dx.length; i++) {
                int nextX = cur[0] + dx[i];
                int nextY = cur[1] + dy[i];

                if (nextX >= 0 && nextY >= 0 && nextX < map.length && nextY < map[0].length && map[nextX][nextY] == 1) {
                    map[nextX][nextY] = 0;
                    queue.offer(new int[]{nextX, nextY});
                }
            }
        }

        return cnt;
    }
}

DFS / BFS (깊이 탐색 / 너비 탐색)에서 중요한 점

• 기본 형태는 대부분 동일한 구성으로 되지만 반복되는 범위와 조건들의 부여하는 방법을 찾아내는 게 주요 관점이다.
  • 배열 혹은 수를 기준으로 하는 경우가 많다.
  • 일반적으로 깊이 탐색은 현재 점을 기준으로 비교하고 너비 탐색은 다음 점을 기준으로 비교한다.
  • 너비 탐색의 경우 지나간 지점을 반복하지 않도록 체크를 해주는 부분이 필요하다.
• 너비 탐색에서 큐에 담는 값은 횟수나 크기등 다양한 값이 필요할 경우가 있어 배열을 이용할 수도 있고 클래스를 만들어서 이용하는 경우도 많다.
• 깊이 탐색과 너비 탐색 중 어떤 알고리즘을 사용해야 적합할지를 모를 때는 먼저 너비 탐색을 고려해 보고 깊이 탐색을 고려해 보면 알고리즘을 생각하기 편했다. (개인적인 생각)