너비 우선 탐색(BFS)

너비 우선 탐색(Breadth First Search)이란

시작 노드에서 인접 노드를 모두 방문하고, 방문한 노드에서 인접 노드를 모두 방문하는 것을 반복하게 된다.

BFS - 큐로 구현

public class BfsEx1 {

    static final int MAX_N = 10;
    static int N, E;
    static int[][] GRAPH = new int[MAX_N][MAX_N];

    static void bfs(int node) {
        boolean[] visited = new boolean[MAX_N];

        Queue<Integer> myQueue = new LinkedList<>();
        visited[node] = true;
        myQueue.add(node);

        while(!myQueue.isEmpty()) {
            int current = myQueue.remove();

            System.out.print(current + " ");

            for(int next = 0; next < N; next++) {
                if(!visited[next] && GRAPH[current][next] != 0) {
                    visited[next] = true;
                    myQueue.add(next);
                }
            }
        }
    }

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

        for(int i = 0; i < E; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            GRAPH[u][v] = GRAPH[v][u] = 1;
        }

        bfs(0);
    }
}

BFS - Shortest path 구현

public class BfsEx2 {

    static final int MAX_N = 10;
    static int[][] D = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static int N;
    static int[][] BOARD = new int[MAX_N][MAX_N];
    static class Point {
        // 행, 열, 거리
        int row, col, dist;
        Point(int r, int c, int d) {
            this.row = r;
            this.col = c;
            this.dist = d;
        }
    }

    // 최단 경로 길이 반환
    static int bfs(int sRow, int sCol, int dRow, int dCol) {

        boolean[][] visited = new boolean[MAX_N][MAX_N];
        Queue<Point> myQueue = new LinkedList<>();
        visited[sRow][sCol] = true;
        // 처음 시작 위치는 거리가 0
        myQueue.add(new Point(sRow, sCol, 0));

        while(!myQueue.isEmpty()) {
            Point current = myQueue.remove();
            // 시작 위치와 도착위치가 같은지 체크
            if(current.row == dRow && current.col == dCol) {
                return current.dist;
            }

            // 상하좌우로 새로운 좌표 생성
            for(int i = 0; i < 4; i++) {
                int newRow = current.row + D[i][0];
                int newCol = current.col + D[i][1];

                // 배열의 범위를 벗어난 경우 체크해서 스킵
                if(newRow < 0 || newRow > N-1 || newCol < 0 || newCol > N-1) {
                    continue;
                }

                // 이미 방문했으면 스킵
                if(visited[newRow][newCol]) {
                    continue;
                }

                // 이동하다가 벽을 만난 경우 스킵
                if(BOARD[newRow][newCol] == 1) {
                    continue;
                }

                visited[newRow][newCol] = true;
                myQueue.add(new Point(newRow, newCol, current.dist+1));
            }
        }

        return -1;
    }

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

        // 좌표 셋팅
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                BOARD[i][j] = sc.nextInt();
            }
        }

        // 시작/도착 위치 셋팅
        int sRow, sCol, dRow, dCol;
        sRow = sc.nextInt();
        sCol = sc.nextInt();
        dRow = sc.nextInt();
        dCol = sc.nextInt();

        System.out.println(bfs(sRow, sCol, dRow, dCol));
    }
}

*참고자료 - https://www.youtube.com/watch?v=yQ7o1Y7X_Rg