[백준] 14442번 : 벽 부수고 이동하기 2

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

---

[BFS]

백준의 벽 부수고 이동하기 시리즈 2번째 문제. 1번 문제의 경우 벽을 1개만 부실 수 있었다면 이 문제는 최대 10개를 부실 수 있다. 따라서 1과 유사하게 풀되, 배열의 사이즈를 조금 늘리면 되겠다.

 

int[][][] dist = new int[1001][1001][11];

 

큐에 들어가야할 원소의 개수는 3개이다. 다음 위치의 y좌표, x좌표, 벽을 몇 개 부수었는지. 그래서 만약 다음 위치가 벽이고, 현재 k개 이하로 벽을 부수었다면 (+ visit[ny][nx][crush + 1]을 방문하지 않았다면) 벽을 부수고 이동한다.

파란색으로 색칠한 문장을 구현하지 않아서 TLE를 왕창 만나버렸다.

 

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static class Point{
        int y, x, crush;
        public Point(int yy, int xx, int cc){
            y=yy; x=xx; crush=cc;
        }
    }
    static int[][][] dist = new int[1001][1001][11];
    static char[][] map = new char[1001][1001];
    static boolean[][][] visit = new boolean[1001][1001][11];
    static int[] Y = {-1, 1, 0, 0}, X = {0, 0, -1, 1};
    static int min = 1000000000;

    static void BFS(int r, int c, int k){

        Queue<Point> Q = new LinkedList<>();

        visit[1][1][0] = true;
        dist[1][1][0] = 1;
        Q.add(new Point(1, 1, 0));

        while(!Q.isEmpty()){
            Point p = Q.poll();

            int crush = p.crush;
            int d = dist[p.y][p.x][crush];
            
            if(p.y == r && p.x == c) {
                min = dist[p.y][p.x][crush];
                break;
            }

            for(int a=0; a<4; a++){
                int ny = p.y+Y[a];
                int nx = p.x+X[a];
                int nd = d + 1;

                if(ny < 1 || nx < 1 || ny > r || nx > c || visit[ny][nx][crush]) continue;

                if(map[ny][nx] == '0') {
                
                    visit[ny][nx][crush] = true;
                    dist[ny][nx][crush] = nd;
                    Q.add(new Point(ny, nx, crush));
                }
                else if(map[ny][nx] == '1' && crush < k && !visit[ny][nx][crush + 1]){
                
                    visit[ny][nx][crush + 1] = true;
                    dist[ny][nx][crush + 1] = nd;
                    Q.add(new Point(ny, nx, crush + 1));
                }

            }
        }
    }

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        for(int i=1; i<=n; i++){
            char[] str = br.readLine().toCharArray();
            for(int j=1; j<=m; j++)
                map[i][j] = str[j-1];
        }

        BFS(n, m, k);

        System.out.println(min == 1000000000? -1:min);
    }
}