BOJ 1261 알고스팟

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    // 동, 서, 남, 북
    static int[] dy = {0, 0, 1, -1};
    static int[] dx = {1, -1, 0, 0};
    static int N, M, res;
    static int[][] map;
    static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 1. 입력 받기.
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        for(int i=0; i<N; i++){
            String str = br.readLine();
            for(int j=0; j<M; j++){
                map[i][j] = Integer.parseInt(str.charAt(j)+"");
            }
        }

        // 2. 자료형 준비
        res = 0;
        visited = new boolean[N][M];

        // 3. 0,0에서 BFS 수행.
        bfs(0, 0);

        // 4. 정답 출력
        System.out.println(res);
    }

    static void bfs(int startY, int startX){
        visited[startY][startX] = true;
        Comparator<Data> comparator = new Comparator<Data>(){
            @Override
            public int compare(Data o1, Data o2){
                return Integer.compare(o1.value, o2.value);
            }
        };

        PriorityQueue<Data> pq = new PriorityQueue<>(comparator);
        pq.offer(new Data(startY, startX, 0));
        while(!pq.isEmpty()){
            Data data = pq.poll();
            int y = data.y;
            int x = data.x;
            int value = data.value;


            for(int d=0; d<4; d++){
                int ny = y + dy[d];
                int nx = x + dx[d];

                if(ny < 0 || ny >= N || nx < 0 || nx >= M) continue;

                // 0일때랑 1일때랑 구분해서 해야하네;;
                if(!visited[ny][nx] && map[ny][nx] == 0){
                    visited[ny][nx] = true;
                    pq.offer(new Data(ny, nx, value));
                }else if(!visited[ny][nx] && map[ny][nx] == 1){
                    visited[ny][nx] = true;
                    pq.offer(new Data(ny, nx, value+1));
                }

                if(ny==N-1 && nx==M-1){
                    res = value;
                    return;
                }
            }
        }
    }

    static class Data{
        int y, x, value;
        Data(int y, int x, int value){
            this.y = y;
            this.x = x;
            this.value = value;
        }
    }
}