백준- 2178 미로탐색

www.acmicpc.net/problem/2178

2178번: 미로 탐색

---

BFS를 이용하여 탐색

가장 최단경로만 구하는문제 -> BFS사용

arr[i][j]가 N-1,M-1에 도달했을때 cnt값을 저장 &  BFS를 탈출

---

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
//dfs는 무조건 최단경로만 구해줌
public class 미로탐색 {
	static int N,M;
	static int [][]arr;
	static boolean visit[][];
	static int res;//몇칸만에 이동했는지 출력할변수
	static class Point{//좌표와 이동한 칸수를 저장할 객체
		int r;
		int c;
		int cnt;
		public Point(int r, int c, int cnt) {
			super();
			this.r = r;
			this.c = c;
			this.cnt = cnt;
		}
	}
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input/미로탐색.txt"));
		Scanner sc = new Scanner(System.in);
		N=sc.nextInt();//행
		M=sc.nextInt();//열
		arr = new int[N][M];//인덱스0부터시작
		visit = new boolean[N][M];
		res=0;//최종칸수 저장할 static변수
		for (int i = 0; i < N; i++) {
			String str = sc.next();
			for (int j = 0; j < M; j++) {
				arr[i][j] = str.charAt(j)-'0';//char->int로 바꾸어서 저장
			}
		}
//		print();//배열입력확인
		bfs();
		System.out.println(res);//최종이동칸수 출력
		
		
		
	}
	static int [] dr = {-1,1,0,0};//상하좌우
	static int [] dc = {0,0,-1,1};
	private static void bfs() {
		Queue<Point> Q = new LinkedList<Point>();
		Q.offer(new Point (0,0,1));//배수밭의 0,0 인덱스에서 시작, 시작점도 이동경로에 포함이므로 cnt를 1부터 시작
		visit[0][0]=true;//처음에 방문표시
		while(!Q.isEmpty()) {
			Point v=Q.poll();
			if(v.r ==N-1 && v.c ==M-1) {//만약 N,M에 도착했다면
				res = v.cnt;//cnt값을 저장
				break;//bfs탈출
			}
			for (int k = 0; k <4; k++) {//4방탐색
				int nr = v.r + dr[k];
				int nc = v.c + dc[k];
				if(nr>=0 && nr<N && nc>=0 && nc<M && arr[nr][nc]==1 && !visit[nr][nc]) {//만약 arr[nr][nc]==1이고 방문X면
					Q.add(new Point(nr,nc,v.cnt+1));//큐에넣음, cnt+1
					visit[nr][nc]=true;//방문체크
				}
			}
			
		}
		
		
	}
	private static void print() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				System.out.print(arr[i][j]+" ");
			}System.out.println();
		}
	}

}