백준 2178 미로탐색 / JAVA

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

2178번: 미로 탐색

 

public class boj_2178_mazeSrch_BFS {
	
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	static int N,M;
	static int[][] arr;
	static boolean[][] visited;
	static class Node {
		int x, y;
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		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+1][M+1];
		visited = new boolean[N+1][M+1];
		
		// 미로그리기
		for(int i = 1; i <= N; i++) {
			String s = br.readLine();
			for(int j = 1; j <= M; j++) {
				arr[i][j] = s.charAt(j-1) - '0';
			}
		}

		bfs(1,1);
		
		System.out.println(arr[N][M]);
	}

	public static void bfs(int x, int y) {
		Queue<Node> queue = new LinkedList<>();
		queue.offer(new Node(x,y));
		visited[x][y] = true; // 방문했다
		
		while(!queue.isEmpty()) {
			Node node = queue.poll();
			for(int i = 0; i < 4; i++) {
				int nx = node.x + dx[i];
				int ny = node.y + dy[i];
				if(nx >= 1 && nx <= N && ny >= 1 && ny <= M) {
					if(visited[nx][ny] == false && arr[nx][ny] != 0) {
						arr[nx][ny] = arr[node.x][node.y] + 1; // 이동을 카운팅해준다
						visited[nx][ny] = true;
						queue.offer(new Node(nx,ny));
					}
				}
			}
		}
	}
}