14442 : 벽 부수고 이동하기 2 - JAVA

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

벽 부수고 이동하기 시리즈의 두번째 문제이다.

1은 1학년때 말기에 풀었기에 4년이 넘게 지난 지금, 아무런 기억이 나지 않아서 고민을 여러번 한 문제이다.

나는 기존 풀이를 참고하여 벽 뚫을 수 있는 횟수를 계산하는 배열을 추가했다. 벽을 부술수 없는 상태일 경우 더이상 벽을 부술수 없게 하는 장치가 필요했기 때문이다.  어떤 칸에 도달했을 때 나는 벽을 부술 수 있을 수도 있고, 그렇지 않을수도 있기 때문이다. 큐에 현재만의 최적 상태를 넣는다고 해서, 완전 최적상태를 찾을수 있음을 단언할 수 없다. 

 

핵심 로직은 다음과 같다. 잘 알고있듯 큐에 좌표와 거리, 브레이크 카운터를 저장하고, 브레이크 카운터가 차기 전까지는 벽을 부수고 이동할수 있게끔 코드를 짰다.

뚫을수 없을때는 큐에 아무것도 추가가 안된채로 반복문 초장으로 돌아간다.

            for(int i = 0; i < 4; i++){
                int mx = dx[i] + nd.x;
                int my = dy[i] + nd.y;
                if(mx < 0 || my < 0 || mx >= n || my >= m) continue;
                //안 막혔을 경우
                if(map[mx][my] == 0 && !check[mx][my][nd.bc]){
                    check[mx][my][nd.bc] = true;
                    q.add(new Node(mx, my, nd.dist+1, nd.bc));
                }
                //막힘
                else{
                    //뚫을수 있을때
                    if(nd.bc < k && !check[mx][my][nd.bc+1]){
                        check[mx][my][nd.bc+1] = true;
                        q.add(new Node(mx, my, nd.dist+1, nd.bc+1));
                    }
                }
            }

 

소스코드

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

public class Main {
    static int n, m, k, ans=-1;
    static int[][] map;
    static boolean[][][] check;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        check= new boolean[n][m][k+1];
        String s;
        for(int i = 0; i < n; i++){
            s = br.readLine();
            for(int j = 0; j < m; j++){
                map[i][j] = Integer.parseInt(String.valueOf(s.charAt(j)));
            }
        }
        bfs();
        bw.write(String.valueOf(ans));
        bw.flush();
        bw.close();
        br.close();
    }
    public static void bfs(){
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(0, 0, 1, 0));
        check[0][0][0] = true;
        while(!q.isEmpty()){
            Node nd = q.poll();
            if(nd.x == n-1 && nd.y == m-1){
                ans = nd.dist;
                break;
            }
            for(int i = 0; i < 4; i++){
                int mx = dx[i] + nd.x;
                int my = dy[i] + nd.y;
                if(mx < 0 || my < 0 || mx >= n || my >= m) continue;
                //안 막혔을 경우
                if(map[mx][my] == 0 && !check[mx][my][nd.bc]){
                    check[mx][my][nd.bc] = true;
                    q.add(new Node(mx, my, nd.dist+1, nd.bc));
                }
                //막힘
                else{
                    //뚫을수 있을때
                    if(nd.bc < k && !check[mx][my][nd.bc+1]){
                        check[mx][my][nd.bc+1] = true;
                        q.add(new Node(mx, my, nd.dist+1, nd.bc+1));
                    }
                }
            }
        }
    }
    public static class Node{
        int x, y, dist, bc;
        Node(int x, int y, int dist, int bc){
            this.x = x;
            this.y = y;
            this.dist = dist;
            this.bc = bc;
        }
    }
}