[BOJ 2178] 미로 탐색 (java)

문제 링크 https://www.acmicpc.net/problem/2178

문제풀이

package basics_600;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ2178 {
	static int[][] board;
	static boolean[][] visited;
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };
	static int N;
	static int M;

	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());
		board = new int[N + 1][M + 1];
		visited = new boolean[N + 1][M + 1];

		// 미로 입력
		for (int i = 0; i < N; i++) {
			String[] temp = br.readLine().split("");
			for (int j = 0; j < M; j++) {
				board[i][j] = Integer.parseInt(temp[j]);
			}
		}

		bfs(0, 0);
		System.out.println(board[N-1][M-1]);

	}

	static void bfs(int x, int y) {
		//0,0 방문했으니까 true 
		visited[x][y] = true;

		//x,y묶어서 Queue 1개로 써도 되지만 알아보기 편해서 
		Queue<Integer> queueX = new LinkedList<>();
		Queue<Integer> queueY = new LinkedList<>();

		//방문한 x,y좌표 큐에 추가 
		queueX.offer(x);
		queueY.offer(y);

		//모든 노드 방문할때까지 
		while (!queueX.isEmpty()) {
			int tempX = queueX.poll();
			int tempY = queueY.poll();

			//방문한 노드에서 상,우,하,좌 순으로 탐색 
			for (int i = 0; i < 4; i++) {
				int moveX = tempX + dx[i];
				int moveY = tempY + dy[i];

				//board범위 내에 있고 
				if (moveX >= 0 && moveY >=0 && moveX < N && moveY < M) {
					//방문하지 않았으며 1이라서 이동 가능할때는 
					if (!visited[moveX][moveY] && board[moveX][moveY] == 1) {
						//방문 ! -> true 
						visited[moveX][moveY] = true;
						//큐에 방문할 x,y좌표 넣어준다 
						queueX.offer(moveX);
						queueY.offer(moveY);
						//방문할때마다 +1 씩 증가해서 nxm까지 더하기 
						board[moveX][moveY]= board[tempX][tempY]+1;

					}
				}
			}

		}

	}

}