[알고리즘] BFS DFS

BFS : 그래프에서의 너비 우선 탐색 알고리즘 

DFS와 다르게 가까운 곳부터 차례대로 탐색하는 알고리즘이다.

(DFS는 한 방향으로 끝까지 탐색한 뒤 돌아가는 방식)

 

 

BFS 알고리즘 코드 템플릿

자다가도 벌떡 일어나서 짤 수 있어야 훌륭한 개발자가 된다고 한다.

import java.util.*;

public class Main {

    // 1이 파란 칸, 0이 빨간 칸에 대응
    // 실제로 문제를 풀 때는 2차원 배열을 콘솔에서 입력을 받는다.
    static int[][] board = {
            {1,1,1,0,1,0,0,0,0,0},
            {1,0,0,0,1,0,0,0,0,0},
            {1,1,1,0,1,0,0,0,0,0},
            {1,1,0,0,1,0,0,0,0,0},
            {0,1,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0,0}
    };

    // 해당 칸을 방문했는지 여부를 저장, boolean 2차원 배열로 선언, 주로 board와 같은 사이즈로 만든다.

    static int n = 7, m = 10; // n = 행의 수, m = 열의 수
    static boolean[][] visited = new boolean[n][m];

    static int[] dx = {1, 0, -1, 0}; // dx, dy 의 d는 변하는 값을 의미
    static int[] dy = {0, 1, 0, -1}; // 상하좌우 네 방향을 의미

    public static void main(String[] args) {
        Queue<Pair> Q = new ArrayDeque<>();
        visited[0][0] = true; // (0, 0)을 방문했다고 명시

        Q.offer(new Pair(0, 0)); // 큐에 시작점인 (0, 0)을 삽입

        while (!Q.isEmpty()) {
            Pair cur = Q.poll();
            int curX = cur.x;
            int curY = cur.y;
            // 디버깅용 로그
            System.out.print("(" + curX + ", " + curY + ") -> ");

            for (int i = 0; i < 4; i++) { // 상하좌우 칸을 살펴볼 것이다, 상 하 좌 우 총 4회 반복

                int nx = curX + dx[i]; // nx, ny 의 n은 next
                int ny = curY + dy[i]; // nx, ny에 i에서 정한 방향의 인접한 칸의 좌표가 들어감
                // i = 0 일땐 nx = 1, ny = 0 => 현재 좌표에서 x축으로 1, y축으로 0 이동한 칸 (오른쪽 칸)
                // i = 1 일땐 nx = 0, ny = 1 => 현재 좌표에서 x축으로 0, y축으로 1 이동한 칸 (아래 칸)
                // i = 2 일땐 nx = -1, ny = 0 => 현재 좌표에서 x축으로 -1, y축으로 0 이동한 칸 (왼쪽 칸)
                // i = 3 일땐 nx = 0, ny = -1 => 현재 좌표에서 x축으로 0, y축으로 1 이동한 칸 (윗 칸)

                // nx, ny 좌표 유효성 검증
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 범위 밖일 경우 넘어감
                if (visited[ny][nx] || board[ny][nx] != 1) continue; // 이미 방문한 칸이거나 파란 칸이 아닐 경우

                visited[ny][nx] = true; // (nx, ny)를 방문했다고 명시
                Q.offer(new Pair(nx, ny));
            }
        }
    }

    static class Pair {
        int x;
        int y;

        // int distance; 문제에 따라 거리 변수, 시간 변수, cnt 변수 등 값들이 추가로 들어간다.

        Pair (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

 

<BFS 알고리즘을 구현할 때 주의해야 할 사항>

- 시작점 위치를 방문 표시하기

- 큐에서 빼낼 때 방문 표시를 하지 말고 큐에 넣을 때 방문 표시 하기

(같은 칸이 큐에 여러 번 들어가게 되면서 시간 초과, 메모리 초과가 발생할 수 있다.

- 인접 원소가 범위를 벗어나지 않았는지 잘 확인하기

- x, y, 행, 열 주의

 

 

BFS 알고리즘을 사용해야 하는 경우

- "최소", "최단", "가장 빠른" 키워드

- 시작점에서 거리별로 정보가 필요할 때

 

- 답이 비교적 가까운 곳에 있을 때

- 최단 경로(미로 탈출, 네트워크에서의 최소 홉 수), 레벨 별 탐색(트리의 레벨 순회), 넓게 퍼져서 찾는 것이 효율적일 때

 

 

DFS : 그래프에서의 깊이 우선 탐색 알고리즘 

DFS 알고리즘 코드 템플릿

import java.util.*;

public class Main {
    static int[][] board = {
        {1,1,1,0,1,0,0,0,0,0},
        {1,0,0,0,1,0,0,0,0,0},
        {1,1,1,0,1,0,0,0,0,0},
        {1,1,0,0,1,0,0,0,0,0},
        {0,1,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0}
    }; // 1이 파란 칸, 0이 빨간 칸
    static boolean[][] vis = new boolean[502][502]; // 방문 여부
    static int n = 7, m = 10; // 행, 열
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,1,0,-1}; // 상하좌우

    public static void main(String[] args) {
        Stack<int[]> S = new Stack<>();
        vis[0][0] = true; // 시작점 방문 처리
        S.push(new int[]{0, 0});

        while(!S.isEmpty()) {
            int[] cur = S.pop();
            System.out.print("(" + cur[0] + ", " + cur[1] + ") -> ");
            
            for(int dir = 0; dir < 4; dir++) {
                int nx = cur[0] + dx[dir];
                int ny = cur[1] + dy[dir];

                if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 범위 체크
                if(vis[nx][ny] || board[nx][ny] != 1) continue; // 방문했거나 파란 칸 아니면 skip

                vis[nx][ny] = true;
                S.push(new int[]{nx, ny});
            }
        }
    }
}

 

BFS에서 큐를 스택으로 변경하면 DFS가 된다.

한 방향으로 먼저 끝까지 탐색한 뒤 다른 방향으로 탐색한다.

 

스택을 이용한 DFS, 재귀를 이용한 DFS가 있다.

DFS + 백트래킹 유형으로 자주 나온다.