kingsubin

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

public class boj_2206 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N, M, nx, ny;
    static int[][] map;
    static boolean[][][] v;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static Queue<int[]> q = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        int ans = -1;
        map = new int[N+1][M+1];
        v = new boolean[N+1][M+1][2];

        for (int i = 1; i <= N; i++) {
            String str = br.readLine();
            for (int j = 1; j <= M; j++) {
                map[i][j] = str.charAt(j-1) - '0';
            }
        }

        v[1][1][0] = true;
        q.offer(new int[] {1, 1, 1, 0});

        while (!q.isEmpty()) {
            int[] now = q.poll();

            if (now[0] == N && now[1] == M) {
                ans = now[2];
                break;
            }

            for (int i = 0; i < 4; i++) {
                nx = now[0] + dx[i];
                ny = now[1] + dy[i];

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

                if (map[nx][ny] == 0) {
                    if (v[nx][ny][now[3]]) continue;

                    v[nx][ny][now[3]] = true;
                    q.offer(new int[] {nx, ny, now[2] + 1, now[3]});
                } else {
                    if (now[3] != 0 || v[nx][ny][now[3]+1]) continue;

                    v[nx][ny][now[3]+1] = true;
                    q.offer(new int[] {nx, ny, now[2] + 1, now[3] + 1});
                }
            }
        }

        System.out.println(ans);
    }
}

 

- 실패

 

- 가지고 이동해야 하는 값 x, y, distance, 벽 부순 횟수