[자바] 백준 2178번 미로탐색 (BFS) 2021-06-14

 전형적인 그래프 탐색 문제이며, "최단" 거리+미로의 탈출을 구하여야 함으로 BFS를 써야 한다. 최단 거리를 구하는 문제에서, DFS가 아닌 BFS를 쓰는 이유는 한가지 계층(똑같은 길이나 방법)을 이용해서 한번 이동을 한 거리가 모두 같음이, 자연스럽게 구현이 되기 때문이다. 또한 같은 계층으로써 방문한 노드가 목적지랑 같을시, 계층 한번이동할때(큐에 넣을때) 넣어준 카운트 값으로 쉽게 최단거리를 출력할 수 있다. 또한 미로의 탈출은 깊이우선 탐색을 하게되면, 해답을 찾지못해도, 계속 깊이가 끝날때까지 탐색을 하기에, 비효율 적이다.

 

그래서 난, BFS를 통해 이문제 풀이법을 구현해 보았다. 그러나 내가 이전 포스트에서 쓴 촌수문제에서, 큐에 넣을때(한번 계층이동이 이루어질때) 바로 카운트값을 더해주는것은 맞지만,

"이전 노드에 저장된 카운트값"

에서 더해줘야 한다는 사실을 기억해 내었다(마치 DP처럼). 말로 쉽게 설명이 안되지만, 그냥 전역필드에 count 변수를 +1해줘서 큐에 넣기 전에 더해주는 것이 아니라, 노드를 표현한 클래스를 하나 만든다음, 그 노드하나가 큐에서 poll되서 인접한 노드들을 큐에 넣을때, 이전 노드의 클래스의 인스턴스변수인 카운트값 에서 +1한 값을 새로 큐에 넣는 노드의 카운트 값에 넣어주는 것이다.

무조건 BFS의 최단거리를 풀때는 이런 방식으로 구현해야 한다.(백준 7562번 내 코드 참고 바람. 내가 굳이 이렇게 안해도 된다고 오해한거 같은데 그 이유가 있는 7562번 카운트 올려주는 법을 보면 내가 잘못 본것을 알수 있다. 이전 카운트 값에서 +1 해주는 게 맞다.)

 

import java.io.*;
import java.util.*;

public class Main {
    static boolean[][] value;

    public static void main(String[] args) throws IOException {
        Scanner s = new Scanner(System.in);
        int N = s.nextInt();
        int M = s.nextInt();
        char[][] charr = new char[N][];
        value = new boolean[N][M];
        s.nextLine();

        for (int i = 0; i < N; i++) {
            charr[i] = s.nextLine().toCharArray();//공백없이 주어진 값들을 String에서
            //Integer로 바로 변환 불가함. 이유? 첫 글자가 0일시, 0 액면가로 안나오고 사라짐.
        }

        Point[][] arr = new Point[N][M];
        for (int i = 0; i < charr.length; i++) {
            for (int j = 0; j < charr[i].length; j++) {
                int now = Integer.valueOf(charr[i][j]-48);
                arr[i][j] = new Point(i, j, now, 0);
            }
        }
        bfs(arr,N,M);


    }

    static void bfs(Point[][] arr, int N, int M) {
        Queue<Point> queue = new LinkedList<>();
        Point one = arr[0][0];
        one.count++;
        value[0][0] = true;
        queue.add(one);
        while (!queue.isEmpty()) {
            Point now = queue.poll();
            int count = now.count;
            int i = now.i;
            int j = now.j;
            if(i==N-1&&j==M-1){
                System.out.println(count);
                return;
            }
            if ( i- 1 >= 0 && !value[i-1][j]) {
                Point next = arr[i-1][j];
                next.count = count + 1;
                queue.add(next);
                value[i-1][j] = true;
            }
            if (i + 1 < N && !value[i+1][j]) {
                Point next = arr[i+1][j];
                next.count = count + 1;
                queue.add(next);
                value[i+1][j] = true;
            }
            if (j - 1 >= 0 && !value[i][j-1]) {
                Point next = arr[i][j-1];
                next.count = count + 1;
                queue.add(next);
                value[i][j-1] = true;

            }
            if (j+1 < M && !value[i][j+1]) {
                Point next = arr[i][j+1];
                next.count = count + 1;
                queue.add(next);
                value[i][j+1] = true;

            }


        }
    }
}

class Point {
    int i, j;
    int num;
    int count;

    public Point(int i, int j, int num, int count) {
        this.i = i;
        this.j = j;
        this.num = num;
        this.count = count;
    }

    public Point(int num, int count) {
        this.num = num;
        this.count = count;
    }
}

 이렇게 구현 해 보았는데, 오답이 나왔다. 이유는, 주어진 방법(상,하,좌,우)로 "한번" 이동하는 것을, "한번"계층이 이동한 것으로 표현은 잘 했다. 그러나, 조건 하나(0인 곳은 지나갈 수 없다.)를 뺴먹어서 항상 (1,1)부터 (N,M)까지의 최단거리 가 출력된다.

 if ( i- 1 >= 0 && !value[i-1][j]&&arr[i-1][j].num==1) {
                Point next = arr[i-1][j];
                next.count = count + 1;
                queue.add(next);
                value[i-1][j] = true;
            }
            if (i + 1 < N && !value[i+1][j]&&arr[i+1][j].num==1) {
                Point next = arr[i+1][j];
                next.count = count + 1;
                queue.add(next);
                value[i+1][j] = true;
            }
            if (j - 1 >= 0 && !value[i][j-1]&&arr[i][j-1].num==1) {
                Point next = arr[i][j-1];
                next.count = count + 1;
                queue.add(next);
                value[i][j-1] = true;

            }
            if (j+1 < M && !value[i][j+1]&&arr[i][j+1].num==1) {
                Point next = arr[i][j+1];
                next.count = count + 1;
                queue.add(next);
                value[i][j+1] = true;

            }

 

각 조건마다, 내가 빠트린 조건을 입력해 보았다. 그러니 정상적으로 답이 나왔다.

 

*내가 한 실수들* 

실수 1: nextInt() 메서드 바로 다음에 nextLine()쓰면 안됨, 왜냐하면 입력스트림에 엔터가 남아있어서 바로 다음 라인은 입력이 다 된것으로 프로그램이 인식해서 한칸 입력 못받음.

실수 2: 배열의 [i][j]는 평면좌표의 [x][y] 가 아님, 왜냐하면 배열은 행 우선이기 때문에 굳이 말하자면 i가 x가 아닌, j임.실

실수 3: 0이면 방문할수 없다는 조건을 빼먹음.

 

-추가-

코드가 너무 길고 지저분해 보였다. 그래서 각 노드가 이동할수 있는 경우의 수 4가지(상,하, 좌,우)를 배열에 담고 for문을 통해 각 배열을 더해줘서 노드를 이동 시켜주는 쪽으로 한번 바꾸어 보았다. (일반적인 BFS 최단거리 방법)

 while (!queue.isEmpty()) {
            Point now = queue.poll();
            int count = now.count;
            int nexti = now.i;
            int nextj = now.j;
            if(nexti==N-1&&nextj==M-1){
                System.out.println(count);
                return;
            }
           for(int x=0;x< dx.length;x++){
               nexti=now.i+dx[x];//실수주의: nexti+=dx[x] 이럼 안됨. nexti에 저장되어버림.
               //저장되 버려서 범위가 쉽게 넘어가 버림.
               nextj= now.j+dy[x];
           if(nexti<0||nextj<0||nexti>=N||nextj>=M){
               continue;
           }
           if(value[nexti][nextj]||arr[nexti][nextj].num==0){
               continue;
           }
           Point next=arr[nexti][nextj];
           next.count=count+1;
           queue.add(next);
           value[nexti][nextj]=true;

           }

 이럼 코드가 훨씬더 깔끔하고, 직관적으로 바뀌었다.

 

공부시간: 4시간.

순 공부시간: 2시간.

 

오늘 공부는 한문제만 계속 고민하고, 관련 개념을 공부하며 풀었는데, 전에 내가 잘못알고있었던 것을 확실히 알게 되었고, BFS 개념을 더욱 깊이있게 이해 할 수 있어서 시간이 엄청 알차게 느껴졌다.