백준 2206번 벽 부수고 이동하기 [ Java ]

2206번: 벽 부수고 이동하기

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] dx = new int[]{1, 0, -1, 0};
        int[] dy = new int[]{0, 1, 0, -1};
        Queue<Point> Q = new LinkedList<>();
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] field = new int[n][m];
        int[][] visited = new int[n][m];
        for (int i=0; i<n; i++) {
            field[i] = Arrays.stream(br.readLine().split(""))
                            .mapToInt(Integer::parseInt)
                            .toArray();
            Arrays.fill(visited[i], Integer.MAX_VALUE);
        }
        Q.offer(new Point(0, 0, 0, 0));
        visited[0][0] = 0;
        while (!Q.isEmpty()){
            Point cur = Q.poll();
            if (cur.y == n-1 && cur.x == m-1){
                System.out.print(cur.dist+1);
                System.exit(0);
            }
            for (int dir=0; dir<4; dir++){
                int nx = cur.x + dx[dir];
                int ny = cur.y + dy[dir];
                if (nx<0 || nx>=m || ny<0 || ny>=n) continue;
                // 벽을 부수고 온 것과 안부수고 온 것이 만났을 때
                if (visited[ny][nx] <= cur.drilled) continue;
                if (field[ny][nx] == 0){ // 벽이 아니면
                    Q.offer(new Point(nx, ny, cur.dist+1, cur.drilled));
                    visited[ny][nx] = cur.drilled;
                }else if (cur.drilled == 0){ // 벽이면서 부순적이 없으면
                    Q.offer(new Point(nx, ny, cur.dist+1, 1));
                    visited[ny][nx] = cur.drilled;
                }
            }
        }
        System.out.print(-1);
    }
    static class Point {
        int x, y, dist, drilled;
        public Point(int x, int y, int dist, int drilled){
            this.x = x;
            this.y = y;
            this.dist = dist;
            this.drilled = drilled;
        }
    }
}