백준 16933 - 벽 부수고 이동하기 3

분기처리를 해야한다면 그냥 3차원이든 4차원이든 배열로 처리해준다.

www.acmicpc.net/problem/16933

16933번: 벽 부수고 이동하기 3

 

 

package algorithm;
 
import java.io.*;
import java.util.*;
 
public class B16933 {
 
    static boolean[][][][] visit;
    static int n;
    static int m;
    static int k;
    static int[][][][] count;
    static int[] dx = { 0, 0, 1, -1 };
    static int[] dy = { 1, -1, 0, 0 };
    static int[][] board;
 
    public static class Point {
        int x;
        int y;
        int z;
        int day;
 
        public Point(int x, int y, int z, int day) {
            this.x = x;
            this.y = y;
            this.z = z;
            this.day = day;
        }
    }
 
    public static boolean check(int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < m;
    }
 
    public static void bfs(Point p) {
        Queue<Point> que = new LinkedList<Point>();
        que.add(p);
        visit[p.day][p.x][p.y][p.z] = true;
        while (!que.isEmpty()) {
            Point tmp = que.poll();
            int x = tmp.x;
            int y = tmp.y;
            int z = tmp.z;
            int day = tmp.day;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (check(nx, ny)) {
                    if (day == 0) {
                        // 낮일때 , 벽 부수고 이동하거나 벽 부수지 않고 이동
                        // 벽이라면 부수고 이동
                        // 벽이 아니면 그냥 이동
                        if (board[nx][ny] == 0) {
                            if (!visit[1][nx][ny][z]) {
                                visit[1][nx][ny][z] = true;
                                count[1][nx][ny][z] = count[day][x][y][z] + 1;
                                que.add(new Point(nx, ny, z, 1));
                            }
                        } else {
                            if (z < k && !visit[1][nx][ny][z + 1]) {
                                // 벽부수고 이동 가능
                                visit[1][nx][ny][z + 1] = true;
                                count[1][nx][ny][z + 1] = count[day][x][y][z] + 1;
                                que.add(new Point(nx, ny, z + 1, 1));
                            } else if (z == k) {
                                // 이동 불가능
                                continue;
                            }
                        }
                    } else {
                        // 밤일때는 벽이라면, 부수지못한다
                        // 아니면 벽을 부술수 잇는 낮까지 기다림
                        // 벽이 아니라면 그냥 이동
                        if (board[nx][ny] == 1) {
                            if (z < k) {
                                if(!visit[0][x][y][z]) {
                                visit[0][x][y][z] = true;
                                count[0][x][y][z] = count[day][x][y][z] + 1;
                                que.add(new Point(x, y, z, 0));
                                }
                            }
 
                        } else {
                            if (!visit[0][nx][ny][z]) {
                                visit[0][nx][ny][z] = true;
                                count[0][nx][ny][z] = count[day][x][y][z] + 1;
                                que.add(new Point(nx, ny, z, 0));
                            }
                        }
                    }
                }
            }
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        n = Integer.parseInt(inputs[0]);
        m = Integer.parseInt(inputs[1]);
        k = Integer.parseInt(inputs[2]);
        board = new int[n][m];
        visit = new boolean[2][n][m][k + 1];
        count = new int[2][n][m][k + 1];
 
        for (int i = 0; i < n; i++) {
            inputs = br.readLine().split("");
            for (int j = 0; j < m; j++) {
                board[i][j] = Integer.parseInt(inputs[j]);
            }
        }
        bfs(new Point(0, 0, 0, 0));
        int min = Integer.MAX_VALUE;
        for (int d = 0; d < 2; d++) {
            for (int i = 0; i <= k; i++) {
                if (count[d][n - 1][m - 1][i] != 0) {
                    min = Math.min(min, count[d][n - 1][m - 1][i]);
                }
            }
        }
        if (min == Integer.MAX_VALUE) {
            if (n == 1 && m == 1) {
                System.out.println(1);
            } else {
                System.out.println(-1);
            }
        } else {
            System.out.println(min + 1);
        }
 
    }
}