[백준] 2178 미로 탐색

---

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

public class Main {
	static int[][] xy;
	static int[][] visit;
	static int[] x_move = {0,0,-1,1};
	static int[] y_move = {-1,1,0,0};
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		xy = new int[N][M];
		visit = new int[N][M];
		for(int i = 0; i < N; i++) {
			String str = br.readLine();
			for(int j = 0; j < M; j++) {
				xy[i][j] = str.charAt(j)-'0';
			}
		}
		bfs(N,M);
		System.out.println(visit[N-1][M-1] + 1); //1,1의 방문처리 +1
	}
	static void bfs(int n, int m) {
		Queue<Integer> q = new LinkedList<>();
		q.add(0); //x
		q.add(0); //y
		while(!q.isEmpty()) {
			int x = q.poll();
			int y = q.poll();
			int cnt = 3;
			for(int i = 0; i < 4; i++) {
				int tx = x+x_move[cnt]; 
				int ty = y+y_move[cnt];
				if(tx >= 0 && tx< n && ty >= 0 && ty < m) {
					if(xy[tx][ty] == 1 && visit[tx][ty] == 0) {
						visit[tx][ty] = visit[x][y] + 1;
						q.add(tx);
						q.add(ty);
						cnt = change(cnt);
					}
					else
						cnt = change(cnt);
				}
				else
					cnt = change(cnt);
			}
		}
	}
	static int change(int n) {
		if(n <= 0) {
			return 3;
		}
		else
			return n-1;
	}
}