백준 14442 벽 부수고 이동하기(Java)

https://www.acmicpc.net/problem/14442

14442번: 벽 부수고 이동하기 2

가중치 없는 최단거리 문제는 거의 무조건 BFS이다. 

 

그리고 이 문제를 풀 때 주의할 점은, '벽'이라는 변수가 있기 때문에 방문 체크를 잘 해야한다는 것이다.

 

벽을 부수면서 빠르게 도착점에 근접했더라도, 이미 벽을 부술 수 있는 기회를 다 써버렸다면 도착점에 도달할 수 없다. 

만약 단순 2차원 배열로 매 순간 방문 체크를 True로 했다면, 벽을 부술 수 있는 기회를 지닌 느림보 bfs가 도착점에 근접할 수가 없다. 왜냐하면 이미 방문 체크가 True이기 때문이다. 따라서 이 문제에서는 방문 체크를 3차원 배열로 해야한다.

 

[행][열][벽 부순 개수]

 

이것만 주의하면 어렵지 않은 문제다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

class Pair {
    int r, c, cnt, time;

    Pair(int r, int c, int cnt, int time) {
        this.r = r;
        this.c = c;
        this.cnt = cnt;
        this.time = time;
    }
}

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;

    static int N, M, K;
    static int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
    static boolean[][][] isVisit;
//    static String[] map;
    static char[][] map;
    static Queue<Pair> q = new ArrayDeque<Pair>();

    public static void main(String[] args) throws Exception {
        input();
        solve();
        bw.flush();
    }

    static int pI(String s) {
        return Integer.parseInt(s);
    }

    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = pI(st.nextToken());
        M = pI(st.nextToken());
        K = pI(st.nextToken());

//        map = new String[N+1];
        map = new char[N+1][M+1];
        isVisit = new boolean[N + 1][M + 1][11];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            String temp = st.nextToken();
            for(int j = 0; j < temp.length(); j++){
                map[i][j+1] = temp.charAt(j);
            }
        }
    }

    static boolean isRange(int r, int c) {
        return r >= 1 && r <= N && c >= 1 && c <= M;
    }

    static void solve() throws Exception {
        isVisit[1][1][0] = true;
        q.add(new Pair(1, 1, 0, 1));

        while (!q.isEmpty()) {
            int rr = q.peek().r;
            int cc = q.peek().c;
            int cnt = q.peek().cnt;
            int time = q.peek().time;

            if(rr == N && cc== M ){
                bw.write(""+time);
                return;
            }

            q.poll();

            for (int i = 0; i < 4; i++) {
                int nr = rr + dr[i];
                int nc = cc + dc[i];

                if (isRange(nr, nc)) {
                    // 벽이 있을 때 뚫고 가거나 가지않는다.
                    if(map[nr][nc] == '1'){
                        if(cnt < K && !isVisit[nr][nc][cnt+1]){
                            isVisit[nr][nc][cnt+1] = true;

                            q.add(new Pair(nr, nc, cnt+1, time + 1));
                        }
                    }  else if(!isVisit[nr][nc][cnt]){

                        isVisit[nr][nc][cnt] = true;

                        q.add(new Pair(nr, nc, cnt, time + 1));
                    }
                }
            }
        }

        bw.write(-1+"");
    }
}