[백준] 2178번 미로탐색

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

목표: 2차원 배열에서 출발 위치에서 (N,M)의 위치로 이동할 때 지나야 하는 최소의 칸 수 구하기 BFS 활용- 너비우선 탐색이므로 (N,M)으로 가는 거리 자체가 답이다. map[nx][ny] = map[p.x][p.y] + 1; 을 해줌으로써 이동 거리 횟수를 계속 누적시킨다.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main{
	static int N,M;
	static int[][] map,dir= {{0,1},{1,0},{0,-1},{-1,0}};
	static boolean[][] visited;
	static Queue<Pair> q = new LinkedList();
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		map = new int[N][M];
		visited = new boolean[N][M];
		
		for (int i = 0; i < N; i++) {
			String s = sc.next();
			for (int j = 0; j < M; j++) {
				
				map[i][j] = s.charAt(j)-48;
			}
		}//end of input
		
		bfs();
		System.out.println(map[N-1][M-1]);
		
	}//end of main
	
	public static void bfs() {
		q.offer(new Pair(0, 0));
		visited[0][0] = true;
		while(!q.isEmpty()) {
			Pair p = q.poll();
			
			for (int k = 0; k < 4; k++) {
				int nx = p.x + dir[k][0];
				int ny = p.y + dir[k][1];
				
				if(isInside(nx,ny) && map[nx][ny]==1 && !visited[nx][ny]) {
					q.offer(new Pair(nx,ny));
					visited[nx][ny] = true;
					map[nx][ny] = map[p.x][p.y] + 1;
					
				}
			}
			
		}
		
	}

	public static boolean isInside(int x, int y) {
		return x>=0 && x<N && y>=0 && y<M;
	}
}//end of class
class Pair{
	int x;
	int y;
	
	Pair(int x ,int y){
		this.x = x;
		this.y = y;
	}
}