Maze Search - Minimum Distance

BFS

틀린 이유(틀린 부분)

1. scanner의 nextInt()와 nextLine()을 함께 쓸 땐 반드시 주의해야한다! 앞에서 m,n을 입력받고 난 후 nextLine으로 String을 입력 받을 때, 앞에서 정수와 개행문자(\n)를 함께 입력하면 그 다음 String은 이 개행문자를 String으로 받기 때문에 반드시 nextLine()을 한번 더 넣어주어야 한다!

배운 내용

1. 거리 배열이 있다면 중복 체크 배열은 불필요하다! 최소 거리를 찾기 위해 거리를 저장하는 2차원 배열을 만든다. 디폴트 값은 '-1'로 해주고, 시작하는 위치를 '0'으로 한다. BFS 순회할 때 중복 체크 배열 대신, 이 dist배열 값이 -1이면 그 좌표에 방문하지 않은 것이므로, 인접노드의 좌표를 저장하고 범위체크 후 유효한 범위 내면 입력 배열에서 이동가능한지('1'이면 이동 가능), 중복 방문이 아닌지(dist 값이 '-1') 확인해주면 된다!

2. Scanner.nextLine()으로 공백없이 2차원 배을 입력받는 방법

   Scanner sc = new Scanner(System.in);
   int n = sc.nextInt();
   int m = sc.nextInt();
   int[][] a = new int[n][m];
   sc.nextLine();
   for(int i=0;i<n;i++){
       String s = sc.nextLine();
       for(int j=0;j<m;j++){
           a[i][j] = s.charAt(j)-'0';
       }
   }

   

알고리즘 생각

일단, DFS로 이 문제를 풀 수는 없다. DFS는 이름에서 그러하듯, 깊이 우선으로 탐색하기 때문이다. 그렇기 때문에 BFS로 탐색하면서 현재 위치(x,y)에서부터 거리를 기록하여 마지막에 거리 배열의 마지막 칸인 (n-1,m-1)의 값이 최소 거리 정답이 된다.

Q. 여러번 BFS 탐색을 하고, 그중 (n-1,m-1) 에 이르는 값이 가장 작은 BFS를 찾는 것 아닌가?

A. BFS는 한번에 상,하,좌,우에 인접해있는 노드들을 큐에 넣는다. n번에 걸쳐 큐에 노드를 넣는다면 거리가 n인 노드라고 할 수 있다. (0,0)에서 (x,y)까지 이르는 거리값을 2차원 배열에 저장한다면 (x,y)까지의 최소 거리가 된다!