# 미로탐색(2178) ## 문제 N×M크기의 배열로 표현되는 미로가 있다. | 1 | 0 | 1 | 1 | 1 | 1 | | - | - | - | - | - | - | | 1 | 0 | 1 | 0 | 1 | 0 | | 1 | 0 | 1 | 0 | 1 | 1 | | 1 | 1 | 1 | 0 | 1 | 1 | 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. ### 입력 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 **붙어서** 입력으로 주어진다. ### 출력 첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다. 예제 입력1 ``` 4 6 101111 101010 101011 111011 ``` 예제 출력1 ``` 15 ``` 예제 입력2 ``` 4 6 110110 110110 111111 111101 ``` 예제 출력2 ``` 9 ``` 예제 입력3 ``` 2 25 1011101110111011101110111 1110111011101110111011101 ``` 예제 출력3 ``` 38 ``` 예제 입력 4 ``` 7 7 1011111 1110001 1000001 1000001 1000001 1000001 1111111 ``` 예제 출력 4 ``` 13 ``` ## 풀이 일단 bfs이란 무엇인가에 대해서 이론적으로 확인해보았다. 기본 문제같은 경우이기 때문에 암기가 가장 좋을 것 같다고 생각되어서 이해가 되는대로 문제를 참고해서 풀어보았다. ```java import java.util.*; import java.io.*; public class Main{ static int[][] arr; static int n, m; static boolean[][] visited; public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken()); arr = new int[n][m]; visited = new boolean[n][m]; visited[0][0] = true; for(int i=0; i q = new LinkedList(); //현재 좌표를 넣어주고 q.add(new int[] {x, y}); //이동할 수 있는 가지 수, 동서남북 int[] dx = {1, 0, -1, 0}; int[] dy = {0, 1, 0, -1}; while(!q.isEmpty()){ int[] xy = q.poll(); for(int i=0; i<4; i++){ //동서남북으로 탐색 int nextX = xy[0] + dx[i]; int nextY = xy[1] + dy[i]; //만약 다음으로 넘어가는 곳이 미로를 벗어나거나 //이미 탐색했던 곳이거나 벽이라면 다음 반복문으로 넘어가고 if(nextX<0 || nextX>=n || nextY<0 || nextY>=m || visited[nextX][nextY] || arr[nextX][nextY]==0) continue; //다음 탐색 지점을 큐에 넣고 q.add(new int[] {nextX, nextY}); //탐색했다고 기록을 찍어두고 visited[nextX][nextY] = true; //다음 탐색 지점에 현재 탐색지점+1해서 넣어주자 arr[nextX][nextY] = arr[xy[0]][xy[1]]+1; } } } } ``` 클ㅡ ```java //클래스를 만들어서 문제를 해결하는 방법도 괜찮은 방법이라고 생각해서 다시 복습겸 연습중이다. import java.util.*; import java.io.*; public class Main{ static int n, m; static int[][] arr; static boolean[][] visited; static int[] dx = {0,1,0,-1}; static int[] dy = {1,0,-1,0}; public static class Point{ int x; int y; public Point(int x, int y){ this.x = x; this.y = y; } } public static void main(String[] args)throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken()); arr = new int[n][m]; visited = new boolean[n][m]; for(int i=0; i q = new LinkedList<>(); q.add(point); visited[point.x][point.y] = true; while(!q.isEmpty()){ Point tmp = q.poll(); for(int i=0; i<4; i++){ int nx = tmp.x + dx[i]; int ny = tmp.y + dy[i]; if(nx<0 || nx>=n || ny<0 || ny>=m || visited[nx][ny] || arr[nx][ny]!=1) continue; q.add(new Point(nx, ny)); visited[nx][ny] = true; arr[nx][ny] = arr[tmp.x][tmp.y]+1; } } } } ``` --- # Agent Instructions: 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://kyudo97.gitbook.io/library/baekjoon/dfs-bfs/2178.md?ask= ``` 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.