[인프런/BFS/11. 미로의 최단거리 통로]

<<풀이>>

-나의 풀이-

ㅋㅋ

일단 내가 푼 문제도 정답이긴하다.

 

하지만 BFS라고 적혀있지만 DFS로 푼 것이다 !!

 

(7,7)로 가는 길이의 모든 경우의 수를 구한 뒤에

 

가장 작은 값을 return 해주면 되는 것이다. 만약 Math.min을 안 해주게 된다면 경우의 수 모두 구하면서 가장 마지막 것을 호출하기 때문에 주의가 필요하다.

 

이 문제는 BFS로 풀어야 하는 문제임으로 강사님 풀이를 보며 다시 BFS를 복습했다.

import java.util.Scanner;

class Main {
    static int min = 10000;
    static int answer = 0;
    static int[][] ch = new int[8][8];
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};

    private void BFS(int L, int[][] arr, int row, int column) {

        if (row == 7 && column == 7) {
            answer = L;
          
          min = Math.min(answer, min);

        }
            if (row < 1 || row > 7 || column < 1 || column > 7) {
                return;
            } else if (ch[row][column] != 1 && arr[row][column] == 0) {
                ch[row][column] = 1;
                for (int i = 0; i < 4; i++) {
                    BFS(L + 1, arr, row + dx[i], column + dy[i]);
                }
                ch[row][column] = 0;
            }

        }



    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int[][] arr = new int[8][8];
        for(int i=1; i<=7; i++) {
            for (int j=1; j<=7; j++) {
                arr[i][j] = in.nextInt();
            }
        }
        T.BFS(0, arr, 1, 1);
        System.out.println(min);

    }
}

 

-강사님 풀이-

 

BFS는 너비우선탐색의 줄인 말로써, 큐를 이용해서 구현을 한다. *예전에 공부했지만 BFS는 Q와 while문의 조합 DFS는 if, 스택과 재귀함수의 조합이였다.

 

특히나 BFS는 최단거리를 구해야 하는 문제에서 많이 사용된다.

왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만,

너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 최단거리이기 때문이다.

 

위에 내가 푼 문제를 보면 쉽게 이해할 수 있다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

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

class Main {
    static int[] dx= {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int[][] board, dis;
    private void BFS(int x, int y) {
        Queue<Point> Q = new LinkedList<>();
        Q.offer(new Point(x, y));
        board[x][y] = 1;
        while (!Q.isEmpty()) {
            Point tmp = Q.poll();
            for (int i = 0; i < 4; i++) {
                int nx = tmp.x + dx[i];
                int ny = tmp.y + dy[i];
                if (nx>=1 && nx<=7 && ny>=1 && ny<=7 && board[nx][ny]==0) {
                    board[nx][ny] = 1;
                    Q.offer(new Point(nx, ny));
                    dis[nx][ny] = dis[tmp.x][tmp.y]+1;
                }
            }
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        board = new int[8][8];
        dis = new int[8][8];
        for (int i = 1; i <= 7 ; i++) {
            for (int j = 1; j <= 7; j++) {
                board[i][j] = in.nextInt();
            }
        }
        T.BFS(1,1);
        if (dis[7][7]==0) System.out.println(-1);
        else System.out.println(dis[7][7]);
    }
}

 

무슨 말인지는 이해했으나, 현재는 엄청 크게 와닿지는 못하는 것 같다. 문제를 여러개 풀어보면서 시행착오가 있어야 하는 부분이다.

 

더 열심히 해보자 !!