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

생각 정리

맵에서 0은 이동할 수 있는 곳, 1은 이동할 수 없는 곳(벽이 있는 곳)을 나타낸다.
(1,1)에서 (N,M)까지 이동하려는데 (실제 배열에서는 0,0에서 N-1,M-1) 최단경로 구하기
한개의 벽을 부수는 것으로 경로가 짧아진다면 한개까지 부술 수 있음

1. 벽을 하나씩 깨보면서 그 때마다 최단 경로를 구해서 비교하기

• 벽을 하나씩 깨보면서(1일때마다) 해당 위치는 0으로 바꾸기 (이미 바꾸었다는 표시 해두기)
• 해당 경우의 탐색을 통해 최단 경로를 구하기
• 다시 1로 바꾸어 두기

생각하지 못한 것

벽을 하나씩 부수면 시간초과됨!
벽을 부수고 탐색하는 경우와 벽을 부수지 않고 탐색하는 경우를 나타내는 배열을 둔다.
(3차원 배열을 사용한다.)

• dist[x][y][0] : 벽을 하나도 부수지 않고 (x,y)까지 오는데 걸리는 비용
• dist[x][y][1] : 벽을 하나만 부수고 (x,y)까지 오는데 걸리는 비용, (x,y)가 벽이라서 부수는 경우 포함

코드

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

class Wall {
    int x, y; //현재 map의 위치
    boolean change; //지금까지 벽을 부순적 있는지

    Wall(int x, int y, boolean change) {
        this.x = x;
        this.y = y;
        this.change = change;
    }
}

public class Main {
    static int N, M, r_min = Integer.MAX_VALUE, min = Integer.MAX_VALUE;
    static int[][] map;
    static int[][][] dist; //거리를 나타냄
    static boolean[][][] visited; 
    static boolean flag ;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        dist = new int[N][M][2];
        visited = new boolean[N][M][2];

        int count = 0;

        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<M; j++) {
                map[i][j] = Integer.parseInt(Character.toString(str.charAt(j)));
            }
        }


        bfs(0, 0); 


        
    }

    static void bfs(int x, int y) {
    
        Queue<Wall> queue = new LinkedList<>();
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, -1, 0, 1};
        boolean flag = false;

        if(map[x][y] == 0){ //벽이 아니면
            visited[x][y][0] = true;
            queue.add(new Wall(x, y, false));

        } else {  
            visited[x][y][1] = true;
            queue.add(new Wall(x, y, true)); 

        }

        while(!queue.isEmpty()) {
            Wall out = queue.poll();

            if(out.x == N-1 && out.y == M-1){
                if(out.change)
                    System.out.println(dist[out.x][out.y][1] + 1);
                else
                    System.out.println(dist[out.x][out.y][0] + 1);
               
                flag = true;
                return ;
            }
            for(int i=0; i<4; i++) {
                int nx = out.x + dx[i];
                int ny = out.y + dy[i];

                if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                else if(map[nx][ny] == 0) { //벽이 아닐 때
                    if(!out.change && !visited[nx][ny][0]) { //벽을 부순적이 없다면
                        visited[nx][ny][0] = true;
                        queue.add(new Wall(nx, ny, out.change));
                        dist[nx][ny][0] = dist[out.x][out.y][0] + 1;
                    } 
                    if(out.change && !visited[nx][ny][1]) { //벽을 부순적이 있다면
                        visited[nx][ny][1] = true;
                        queue.add(new Wall(nx, ny, out.change));
                        dist[nx][ny][1] = dist[out.x][out.y][1] + 1;
                    }
                } 
                else if(map[nx][ny] == 1) { //벽일 떄
                    if(!out.change && !visited[nx][ny][0]) { //벽을 부순적이 없으면
                        visited[nx][ny][1] = true;
                        queue.add(new Wall(nx, ny, true));
                        dist[nx][ny][1] = dist[out.x][out.y][0] + 1;
                    }
                }
            }
        }

        if(!flag)
            System.out.println(-1);
    }

    
}