[BOJ] 14442 - 벽 부수고 이동하기 2

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/14442

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

난이도: 골드 3

사용언어: JAVA

 

풀이

기본적으로 BFS를 이용하는 문제이며, 벽을 K번 부술 수 있기 때문에 이를 감안해서 코드를 작성해 주어야 합니다. 

 

메모리 초과를 막기 위해 가장 중요한 아이디어는, 만일 누가 이미 한 번 지나간 경로를 발견했을 때, 해당 경로가 자신보다 더 적거나 같은 수의 벽을 파괴하고 지나왔다면, 해당 경로는 BFS를 수행할 필요가 없다는 것입니다. 이미 지나간 경로가 자신보다 빠르기 때문이죠. 이를 체크해주지 않으면 분명히 메모리 초과 또는 시간 초과와 마주치게 됩니다.

 

이를 구현하기 위해 2차원 배열을 하나 더 만들어 각 칸에 도착할 때마다 자신이 몇 개의 벽을 부수고 왔는지를 기록해줍니다. 그리고 다른 칸에 도착할 때 이미 기록된 정보가 있다면 해당 정보와 비교하여 해당 경로로의 더 이상의 BFS를 수행할지를 결정할 수 있습니다.

 

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
class Main {
 
    static class position {
        int x; // 세로 좌표
        int y; // 가로 좌표
        int c; // 몇 번 더 부술수 있는지
 
        public position(int x, int y, int c) {
            this.x = x;
            this.y = y;
            this.c = c;
        }
    }
 
    static int[][] arr; // 입력을 저장하기 위한 배열
    static int[][] crush; // 부수고 온 벽의 개수를 저장하기 위한 배열
    static Queue<position> q = new LinkedList<>(); // BFS를 위한 큐
    static int cnt = 1;
    static int[][] d = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 움직일 수 있는 방향
    static int N, M, K;
 
    public static void bfs(position p) {
        int i;
        for (i = 0; i < 4; i++) {
            if (arr[p.x + d[i][0]][p.y + d[i][1]] == 0 && crush[p.x + d[i][0]][p.y + d[i][1]] < p.c) { // 칸이 0이고 내가 부수고 온 벽의 수가 기록되있는 것 보다 클 때
                q.add(new position(p.x + d[i][0], p.y + d[i][1], p.c)); // BFS 수행
                crush[p.x + d[i][0]][p.y + d[i][1]] = p.c; // 기록 업데이트
            }
            if (arr[p.x + d[i][0]][p.y + d[i][1]] == 1 && p.c > 1 && crush[p.x + d[i][0]][p.y + d[i][1]] < p.c) { // 칸이 1이고 아직 더 부술 수 있고, 기록보다 클 때
                q.add(new position(p.x + d[i][0], p.y + d[i][1], p.c - 1)); // BFS 수행
                crush[p.x + d[i][0]][p.y + d[i][1]] = p.c - 1; // 기록 업데이트
            }
        }
    }
 
    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());
 
        int i, j, k;
        String s;
        arr = new int[N + 2][M + 2];
        crush = new int[N + 2][M + 2];
        for (i = 1; i <= N; i++) {
            s = br.readLine();
            for (j = 1; j <= M; j++) {
                arr[i][j] = (int) (s.charAt(j - 1) - '0');
            }
        }
 
        for (i = 0; i <= N; i++) { // 테두리를 -1로 감싸줍니다
            arr[i][0] = -1;
            arr[i][M + 1] = -1;
        }
        for (i = 0; i <= M; i++) {
            arr[0][i] = -1;
            arr[N + 1][i] = -1;
        }
 
        if (N == 1 && M == 1 && arr[1][1] == 0) { // 크기가 1x1 일 때 예외처리
            System.out.println("1");
            System.exit(0);
        }
 
        q.add(new position(1, 1, K + 1)); // 첫 칸을 큐에 삽입. crush 배열이 0으로 초기화 되어있기 때문에 1~K+1을 사용
        while (!q.isEmpty()) {
            k = q.size();
            for (i = 0; i < k; i++) {
                position p = q.poll();
                if (p.x == N && p.y == M) { // 목적지 도착
                    bw.write(String.valueOf(cnt) + "\n");
                    bw.flush();
                    bw.close();
                    br.close();
                    System.exit(0);
                }
                bfs(p);
            }
            cnt++;
        }
        bw.write("-1\n"); // 목적지에 도착할 수 없다면
        bw.flush();
        bw.close();
        br.close();
        System.exit(0);
 
    }
}