미로의 최단거리 통로

미로의 최단거리 통로

이전 문제와 동일

입력 설명

첫 번째 줄부터 7*7 격자의 정보가 주어집니다.

출력 설명

첫 번째 줄에 최단으로 움직인 칸의 수를 출력한다. 도착할 수 없으면 -1를 출력한다.

입력

0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 1 0 0 0
1 0 0 0 1 0 0
1 0 1 0 0 0 0

출력

12

틀린 구현 코드

    final static int N = 7;
    static int answer = Integer.MAX_VALUE;
    static int[][] board = new int[N+1][N+1];
    static int[] dir_x = {-1,0,1,0};
    static int[] dir_y = {0,1,0,-1}; //6시 -> 3시 -> 12시 ->9시 방향

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

        for(int i=1;i<N+1;i++){
            for(int j=1;j<N+1;j++){
                board[i][j] = in.nextInt();
            }
        }

        board[1][1] = 1;
        dfs(1,1,0);

        System.out.println(answer);
    }

    static void dfs(int row,int col,int sum){
        if(sum>8*8){
            System.out.println("냥");
            answer = -1;
            return;
        }
        if(row==N && col ==N){
            if(answer>=sum) {
                answer = sum;
                return;
            }
        }
        else{
            //방향보면서 뻗어나가야함
            for(int i=0;i<4;i++){
                int nx = row+dir_x[i];
                int ny = col+dir_y[i];
                if(nx>=1 && nx<=7 && ny>=1 && ny<=7 && board[nx][ny]==0){
                    //경계선 내부에 있고 갈수 있는 지점인지
                    board[nx][ny] = 1;
                    dfs(nx,ny,sum+1);
                    board[nx][ny] = 0;
                }
            }

        }
    }

길이 없어서 닶이 -1이 되는 경우를 어떻게 걸러주지 모르겠어서 처음 해본건 길이 없다면 이리저리 돌테니까 길의 가중치 총합이 8x8인 값을 넘겠지?라는 생각에 sum>88이라는 조건을 걸었음.
문제는 시작 지점에서 얼마 못가서 더이상 갈 길이 없을 수 있음. 따라서 sum>88은 터무니 없는 조건. bfs문제인데 dfs로 풀려해서 더 복잡해졌던 것 같음. 최소문제는 무조건 bfs임을...그리고 queue를 꼭...쓸 것...

모범답안 참고 후 구현 코드

    final static int N = 7;
    static int answer = -1;
    static int[][] board = new int[N+1][N+1];
    static int[] dir_x = {-1,0,1,0};
    static int[] dir_y = {0,1,0,-1}; //6시 -> 3시 -> 12시 ->9시 방향
    static Queue<Point> queue = new LinkedList<>();

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

        for(int i=1;i<N+1;i++){
            for(int j=1;j<N+1;j++){
                board[i][j] = in.nextInt();
            }
        }

        queue.offer(new Point(1,1));
        bfs();

        System.out.println(answer);
    }

    static void bfs(){
        while(!queue.isEmpty()){
            Point p = queue.poll();

            for(int i=0;i<4;i++){
                int nx = p.x +dir_x[i];
                int ny = p.y +dir_y[i];
                if(nx>=1 && nx<=7 && ny>=1 && ny<=7 && board[nx][ny]==0){
                    //경계선 내부에 있고 갈수 있는 지점인지
                    board[nx][ny] = board[p.x][p.y]+1;
                    queue.offer(new Point(nx,ny));
                }
            }
        }

        if(board[N][N] ==0) answer = -1;
        else answer = board[N][N];
    }

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

검사하는 조건은 같고 지금 좌표 = 이전 좌표 + 1; 해가면서 좌표값을 업데이트해주면 됨. bfs라서 queue가 empty가 될때까지 while문 돌면서 진행.
만약 최종 지점으로 갈 길이 없는 경우에는 최종좌표값이 0으로 남아있을 거니까 그런 경우에는 -1을 넣어줌.