백준 2206 벽 부수고 이동하기 java

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

예제 입력의 경우는 벽을 무조건 부숴야 목적지에 도착할 수 있는 형태로 나와있다.

 

문제 조건은 벽을 한번까지 부술 수 있다는 것이고 무조건 벽을 부숴야 하는 상황은 아니기에

벽을 부수고가는 경로와 벽을 부수지 않고 가는 경로를 모두 확인해서 비교해볼 필요가 있다.

 

처음에는 일반적인 bfs의 큐에 들어가는 각 항목에 해당지점까지 가면서 벽을 깼는지 안깼는지를 위한 필드를 추가해서 관리해주면서 최대 1번까지 벽을 깰 수 있도록 구현했는데

 

이렇게 처리하게 된다면 벽을 깨지 않고 a 지점을 거쳤을 때 결론적으론 가장 짧은 루트더라도

벽을 깨지 않았을 때 보다 벽을 깼을 때 a지점에 빠르게 도착한다면, a지점이 visited 처리 되어 벽을 깨지 않고 a지점을 방문할 수 없게되고 결론적으로 최소 길이를 구하지 못하게 된다.

 

예시입력

010010

010110

010110

010110

000110

 

이런 상황일 때 1행 3열의 0 위치에 도달하는 거리를 본다면

시작부터 벽을뚫고 오른쪽으로 이동하면 2칸만에 도달 가능하지만 그럴 때 결국 최종위치에 도달하지 못하고

해당위치는 visited 처리 된다.

그럼 최종위치에 원래 도달할 수 있는 루트인 아래로 쭉 내려갔다가 다시올라왔을 때는 visited되어 있어 방문하지 못하고

결국 적절한 해답을 내지 못한다.

 

그렇기에 visited를 2차원 배열이 아닌 3차원으로 선언해서 관리한다.

visited[row][col][broken]

특정 위치에 한번 부순채로 도달했는지, 부수지 않은채로 도달했는지 관리한다 큐에넣을때 broken을 설정한다는 개념도 그대로 갖고 조합해서 부수고 왔는지, 안부수고왔는지 경우의수를 따지며 bfs를 진행한다.

import java.lang.reflect.Array;
import java.util.*;
import java.io.*;
import java.lang.*;

public class Main {
    /*
    bfs를 쓴다. 벽 부수기 전과 후로 visited를 두가지 쓴다.
    queue에 넣는 것도 row,col,broken으로 한다.
    큐에 있는게 broken이 1이면 visited[][1]이 true인데로 못간다.
     */
    static int rowsize,colsize;
    static class point{
        public int row;
        public int col;
        public int broken;
        point(int row,int col,int broken){
            this.row=row;this.col=col;this.broken=broken;
        }

        @Override
        public String toString() {
            return "point{" +
                    "row=" + row +
                    ", col=" + col +
                    ", broken=" + broken +
                    '}';
        }
    }
    static int[][] arr = new int[1000][1000];
    static Queue<point> q= new ArrayDeque<point>();
    static boolean[][][]visited = new boolean[1000][1000][2];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        StringTokenizer token = new StringTokenizer((str));
        rowsize= Integer.parseInt(token.nextToken());
        colsize= Integer.parseInt(token.nextToken());
        for(int i=0;i<rowsize;i++){
            String string = br.readLine();
            for(int j=0;j<colsize;j++){
                arr[i][j]=Integer.parseInt(string.substring(j,j+1));
            }
        }
        int[]y={0,0,-1,1};
        int[]x={1,-1,0,0};
        q.add(new point(0,0,0));
        int count=0;
        int result=Integer.MAX_VALUE;
        while(!q.isEmpty()){
            int len = q.size();
            for(int i=0;i<len;i++){
                point temp = q.poll();
                if(temp.row==rowsize-1 && temp.col==colsize-1){
                    //System.out.println(temp);
                    result=Math.min(result,count);
                }
                for(int j=0;j<4;j++){
                    int dy= temp.row+y[j];
                    int dx= temp.col+x[j];
                    if(dy<0||dx<0||dy>=rowsize||dx>=colsize) continue;
                    if(temp.broken==1&&visited[dy][dx][1]==true) continue;
                    if(temp.broken==0&&visited[dy][dx][0]==true) continue;
                    if(arr[dy][dx]==1){
                        if(temp.broken==1) continue;
                        else{
                            visited[dy][dx][1]=true;
                            q.add(new point(dy,dx,1));
                        }
                    }
                    else{//벽없는칸일때
                        visited[dy][dx][temp.broken]=true;
                        q.add(new point(dy,dx,temp.broken));
                    }
                    /*
                    temp가 broken==1인경우, visited[1]이 true면 못가.
                    temp가 broken==0이면 visited[0]이 true인곳에 못간다.
                    벽인경우. temp가 broken==1이면 통과불가.
                    broken==0인 경우 broken=1로 add한다.
                     */
                }
            }
            count++;
        }
        if(result== Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(result+1);
    }
}