> 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

**틀린 이유(틀린 부분)**

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 문자열에서 문자 하나하나를 숫자로 저장하는 방법](/files/-Mb1L9IpHip7xa_FsAtv)

**알고리즘 생각**

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


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://heunnajo.gitbook.io/algorithms-problem-solving-skills/graph/maze-search-minimum-distance.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.