> For the complete documentation index, see [llms.txt](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/graph/maze-search-minimum-distance.md).

# 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차원 배을 입력받는 방법**

   ```java
   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';
       }
   }
   ```

   ![String 문자열에서 문자 하나하나를 숫자로 저장하는 방법](https://3269900549-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MIbwNq54Ge4eqsziHM7%2F-Mb1Fuc837S2XBkyKeME%2F-Mb1L9IpHip7xa_FsAtv%2Fimage.png?alt=media\&token=cd3d3dfe-45e4-4cd7-87eb-202529abc466)

**알고리즘 생각**

일단, 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)까지의 최소 거리가 된다!**