[알고리즘][BOJ][2206] 벽 부수고 이동하기

[알고리즘][BOJ][2206] 벽 부수고 이동하기

 

 

문제

https://www.acmicpc.net/problem/2206

 

풀이

꽤 오래걸렸습니다. 중간에 검색을 통해 힌트를 구했습니다. 이 문제도 복습을 꼭 해야겠네요.

 

벽을 부시는 것은 한 번만 가능합니다. 따라서 3중 배열을 활용해 map[x][y][z] 에서 z 자리를 벽을 부신 경우 0, 부시지 않은 경우 1로 구분합니다. 

 

while문 시작 후 step이라는 변수를 두어 칸을 이동할 때마다 거리를 측정합니다. 이 때, 가장 먼저 끝 점에 도달하면 while문을 빠져나오기 때문에 최단거리를 측정하게 됩니다.

 

코드

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

public class Main {
    static int n;
    static int m;
    static int[][] map = new int[1001][1001];
    static boolean[][][] check = new boolean[1001][1001][2];
    
    static int[] dx = {0, -1, 0, 1};
    static int[] dy = {-1, 0, 1, 0};
    static boolean isSuccess;
    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());        

        for(int i=0;i<n;i++) {
            String tmp = br.readLine();
            for(int j=0;j<m;j++) {
                map[i][j] = tmp.charAt(j)-'0';
            }
            
        }
        
        int step = counting_BFS();
        System.out.println(isSuccess? step : -1);
    }
    
    static int counting_BFS() {
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(new Node(0,0,0));
        
        check[0][0][0] = true;
        check[0][0][1] = true;
        
        isSuccess = false;
        int step = 0;
        
        
        while(!queue.isEmpty() && !isSuccess) {
            step++;
            int size = queue.size();
            for(int i=0;i<size;i++) {
                Node node = queue.poll();
                
                if(node.x==n-1 && node.y==m-1) {
                    isSuccess = true;
                    break;
                }
                for(int j=0;j<4;j++) {
                    int nx = node.x + dx[j];
                    int ny = node.y + dy[j];
                
                    if(nx>=0 && nx<n && ny>=0 && ny<m) {
                        //벽의 경우
                        if(map[nx][ny]==1) {
                            //벽을 부시지 않은 상태 && 다음 좌표 방문하지 않았을 경우
                            if(node.destroy<1 && !check[nx][ny][1]){
                                queue.add(new Node(nx,ny,1));
                                check[nx][ny][1]=true;
                            }
                        }
                        //벽이 아닐 경우
                        else {
                            if(!check[nx][ny][node.destroy]) {
                                queue.add(new Node(nx, ny, node.destroy));
                                check[nx][ny][node.destroy]=true;
                            }
                        }
                    }    
                }    
            }    
        }
        return step;
    }
}
class Node{
    int x;
    int y;
    int destroy;
    
    Node(int x, int y, int destroy){
        this.x = x;
        this.y = y;
        this.destroy = destroy;
    }
}