인프런 커뮤니티 질문&답변

예전 BFS 영상에서 최단 경로 길이를 구하기 위해서는 트리 레벨 체크를 활용하는 것을 보고 이번에도 큐 사이즈 만큼 반복을 돌아서 트리 레벨을 체크 하는 방식으로 구현하였는데

프로그램에선 12로 잘 나오지만,

채점에선 오류가 떠서 이 방식으론 안되는지 궁금합니다..

또, 강의를 들으면서 배열에 +1씩 추가하는 아이디어를 보고 기존의 배열에서 +1씩 해주어 수정한 결과는 통과하였는데, DIS배열을 하나 더 만든 이유도 궁금합니다!

추가로 젤 윗 이야기인 큐 사이즈 만큼 반복하여 레벨을 체크하는 상황과 배열에 +1씩 하여 넓혀가는 상황의 구별을 어떻게 할 수 있을지도 궁금해졌습니다...

감사합니다

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

public class In_8_11 {
    static int[][] matrix = new int[8][8];
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int level;
    public static int BFS(int x, int y) {
        Queue<Point> Q = new LinkedList<>();

        // 가장 처음 큐에 넣기
        Q.offer(new Point(x,y));
        matrix[1][1] = 1; // 출발지점 꼭 걸어줘야함.

        // 시작
        while( !Q.isEmpty()){
            for (int j = 0; j < Q.size(); j++) {
                Point P = Q.poll();
                System.out.println("( "+P.x + " , " + P.y+" )");

                if (P.x == 7 && P.y == 7){
                    //return matrix[7][7] -1;
                    return level;
                }

                for (int i = 0; i < 4; i++) {
                    int nx = P.x + dx[i];
                    int ny = P.y + dy[i];

                    if (1 <= nx && nx <= 7 && 1 <= ny && ny <= 7) {
                        if (matrix[nx][ny] == 0) {
                            matrix[nx][ny] = 1;
                            //matrix[nx][ny] = matrix[P.x][P.y] +1; // 뺄 필요 없을 거 같은데?
                            Q.offer(new Point(nx, ny));
                        }
                    }
                }
            }level++;
        }
        return -1;
    }

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