백준저지 14442번 벽 부수고 이동하기 2 (Java)

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

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

 

 

접근 방법

백준저지의 벽 부수고 이동하기(https://www.acmicpc.net/problem/2206) 문제에서 벽의 개수만 추가된 문제다. 그래서 해당 문제의 코드(https://anott.tistory.com/54)와 거의 동일하다. 이전 문제에서는 부순 벽의 개수가 0개일 때만 부수고 이동하게 했다면, 이번에는 K개 이하일 때만 부수고 이동하게 해 주면 된다. 

 

 

 

생각

벽 부수고 이동하기(https://www.acmicpc.net/problem/2206) 문제에서 visited 체크할 때 wall이 아닌 wall+1로 했어도 통과되었다. 그런데 이 문제는 wall+1로 하면 시간 초과가 난다. 현재 위치를 방문했다고 체크하고, 벽은 부순 뒤에서야 방문 체크해야 한다.

 

 

 

코드

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

public class BOJ14442 {

    static int N, M, K, map[][];

    static private class Position {
        int x, y, wall, cnt; // x좌표, y좌표, 벽 부쉈는지 여부, 이동 거리

        public Position(int x, int y, int wall, int cnt) {
            this.x = x;
            this.y = y;
            this.wall = wall;
            this.cnt = cnt;
        }
    }

    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 = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            char[] input = br.readLine().toCharArray();
            for (int j = 0; j < M; j++) {
                map[i][j] = input[j] - '0';
            }
        }
        bw.write(move() + "\n");
        bw.flush();
        bw.close();
    }

    private static int move() { // bfs
        int[][] d = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };
        boolean[][][] visited = new boolean[K + 1][N][M]; // 방문 여부 체크.

        Queue<Position> q = new LinkedList<>();
        q.add(new Position(0, 0, 0, 1)); // 시작
        visited[0][0][0] = true;

        int ccc = 0;

        while (!q.isEmpty()) {
            Position cur = q.poll();

            if (cur.x == N - 1 && cur.y == M - 1) { // 종료 조건
                return cur.cnt;
            }

            for (int i = 0; i < 4; i++) {
                int dx = cur.x + d[i][0];
                int dy = cur.y + d[i][1];
                int wall = cur.wall;
                if (dx < 0 || dx >= N || dy < 0 || dy >= M || visited[wall][dx][dy]) {
                    continue;
                }
                if (map[dx][dy] == 0) { // 0이라면 그냥 이동
                    visited[wall][dx][dy] = true;
                    q.add(new Position(dx, dy, wall, cur.cnt + 1));
                } else if (map[dx][dy] == 1 && wall < K) {
                    visited[wall][dx][dy] = true;
                    q.add(new Position(dx, dy, wall + 1, cur.cnt + 1));
                }
            }
        }

        return -1; // 이동 불가능
    }

}