[백준 2206] 벽 부수고 이동하기

문제 링크 : https://www.acmicpc.net/problem/2206

이 문제는 bfs와 dp(메모리제이션)을 이용해서 풀 수 있습니다.

사실 문제를 처음 접한 후 백트래킹을 이용하여 벽을 부수며 직접 이동하는 방식을 생각했습니다. 하지만 이 경우 최악의 시간 복잡도가 O(2^n)으로 최대 1000X1000개의 경로를 탐색하기 때문에 시간 초과가 발생합니다.

따라서 시간 단축을 위한 메모리제이션 기법을 사용합니다. 벽을 부쉈을 때의 경로와 벽을 부수지 않았을 때의 경로 두 개를 하나의 3차원 배열 내에서 처리하며 상하좌우 움직이면서 현재 이동 횟수를 배열에 기록합니다. 이 때 벽을 부술 수 있을 경우 벽을 부신 경로로 이동하여 새롭게 이동 횟수를 기록합니다.

여기서 저는 bfs를 이용했습니다. bfs 특성상 한 번에 출발점까지 이동하지 않고 이동 가능한 모든 노드들이 한 칸씩 이동하기 때문에 한 번에 도착점까지 이동하여 배열의 위치의 이동 횟수와 자신의 이동 횟수의 최솟값을 계속 비교해야 하는 dfs 메모리제이션과 달리 가장 먼저 도착점에 도달하는 노드가 결국 최솟값이 되므로 연산이 상대적으로 복잡하지 않다는 장점이 있습니다.

다음은 코드입니다.

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

class Main{
    static int N,M,res=-1;
    static int[][][] dp;
    static boolean[][] wall;
    static int[] dy = {1,0,-1,0}, dx = {0,1,0,-1};

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        dp = new int[N][M][2];
        for(int i=0;i<dp.length;i++){
            for(int j=0;j<dp[i].length;j++){
                Arrays.fill(dp[i][j],-1);
            }
        }

        wall = new boolean[N][M];
        for(int i=0;i<N;i++){
            String str = br.readLine();
            for(int j=0;j<M;j++){
                char curr = str.charAt(j);
                if(curr == '0') wall[i][j] = false;
                else if(curr == '1'){
                    wall[i][j] = true;
                    dp[i][j][0] = 0;
                    dp[i][j][1] = 0;
                }
            }
        }

//        dfs(new Player(0,0));
//        int res = Math.min(dp[N-1][M-1][0], dp[N-1][M-1][1]);

        bfs(new Player(0,0, false));
        System.out.println(res);
    }

    static void bfs(Player player){
        dp[player.y][player.x][0] = 1;
        Queue<Player> queue = new LinkedList<>();
        queue.add(player);

        while(!queue.isEmpty()){
            Player curr = queue.poll();

            if(curr.isArrive()){
                res = curr.getDp();
                return;
            }

            for(int i=0;i<4;i++){
                Player next = curr.move(i);

                if(next.canMove()){
                    next.checkNoBreakWall(curr);
                    queue.add(next);
                }
                else if(next.canBreak()){
                    next.checkBreakWall(curr);
                    queue.add(next);
                }
            }
        }
    }

    static class Player{
        int y;
        int x;
        boolean isBroken;

        Player(int y, int x, boolean isBroken){
            this.y = y;
            this.x = x;
            this.isBroken = isBroken;
        }

        Player move(int dir){
            return new Player(
                    y + dy[dir],
                    x + dx[dir],
                    isBroken
            );
        }

        boolean canBreak(){
            if(y<0 || y>=N || x<0 || x>=M) return false;
            if(!wall[y][x]) return false;
            return !isBroken;
        }

        boolean canMove(){
            if(y<0 || y>=N || x<0 || x>=M) return false;
            if(wall[y][x]) return false;
            return dp[y][x][getIdx()] == -1;
        }

        boolean isArrive(){
            return y == N - 1 && x == M - 1;
        }

        int getIdx(){
            return isBroken ? 1 : 0;
        }

        int getDp(){
            return dp[y][x][getIdx()];
        }

        void checkNoBreakWall(Player prev){
            dp[y][x][getIdx()] = dp[prev.y][prev.x][prev.getIdx()]+1;
        }

        void checkBreakWall(Player prev){
            dp[y][x][1] = dp[prev.y][prev.x][prev.getIdx()]+1;
            isBroken = true;
        }
    }
}