[백준] 16933번 : 벽 부수고 이동하기 3 [Java]

#풀이

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


public class Main {
    static int [][] matrix;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int N,M,K;
    static class Point{
        int y;
        int x;
        int dist;
        int countBreak;
        boolean isDay; // true면 벽부수기 가능
        Point(int y,int x, int dist, int countBreak, boolean isDay){
            this.y = y;
            this.x = x;
            this.dist = dist;
            this.countBreak = countBreak;
            this.isDay = isDay;
        }
    }
    static int bfs(){
      int[][][][] visited = new int[2][K+1][N][M];
      //int[][] breakWall = new int[N][M];
      Queue<Point> q = new LinkedList<>();
      q.add(new Point(0,0,1,0,true) );
      visited[0][0][0][0] = 1;
      while(!q.isEmpty()){
          Point temp = q.poll();
          if(temp.y == N-1&& temp.x ==M-1)return temp.dist;
          for(int i = 0; i<4; i++){
              int ty = temp.y + dy[i];
              int tx = temp.x + dx[i];
              if(ty<0||tx<0||ty>N-1||tx>M-1)continue;
              if(matrix[ty][tx]==0) { // 벽안뚫 경우
                  if(temp.isDay) {
                      if (visited[0][temp.countBreak][ty][tx] ==
                      0 || visited[0][temp.countBreak][ty][tx] > temp.dist + 1 )
                      {
                          q.add(new Point(ty, tx, temp.dist + 1, temp.countBreak, !temp.isDay));
                          visited[0][temp.countBreak][ty][tx] = temp.dist + 1;
                      }
                  }
                  else{
                      if (visited[1][temp.countBreak][ty][tx] ==
                              0 || visited[1][temp.countBreak][ty][tx] > temp.dist + 1 )
                      {
                          q.add(new Point(ty, tx, temp.dist + 1, temp.countBreak, !temp.isDay));
                          visited[1][temp.countBreak][ty][tx] = temp.dist + 1;
                      }
                  }
              }
              else{ //벽뚫 경우
                  if(temp.countBreak<K){
                      if(temp.isDay&&(visited[0][temp.countBreak+1][ty][tx]==0||visited[0][temp.countBreak+1][ty][tx] > temp.dist + 1 )){//바로 뚫기 가능
                          q.add(new Point(ty,tx,temp.dist+1, temp.countBreak+1,!temp.isDay ));
                          visited[0][temp.countBreak+1][ty][tx] = temp.dist +1;

                      }
                      else if(!temp.isDay&&(visited[1][temp.countBreak][temp.y][temp.x]==0||visited[1][temp.countBreak][temp.y][temp.x] > temp.dist + 1 )){ //기다려야됨 가만히 있는경우
                          q.add(new Point(temp.y, temp.x, temp.dist+1, temp.countBreak,!temp.isDay ));
                          visited[1][temp.countBreak][temp.y][temp.x] = temp.dist +1;

                      }
                  }
              }
          }
      }
      return -1;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        K = Integer.parseInt(input[2]);
        matrix = new int[N][M];
        for(int i = 0; i<N; i++){
            input = br.readLine().split("");
            for(int k = 0; k<M; k++){
                matrix[i][k] = Integer.parseInt(input[k]);
            }
        }
        int ans = bfs();
        System.out.println(ans);
    }



}

#성능

#정리

방문 여부는 낮/밤 상태, 벽 부순 횟수, 좌표를 기준으로 visited[isDay][벽부순횟수][y][x] 형태로 관리해 같은 좌표라도 상태에 따라 독립적으로 탐색한다. 매 이동마다 낮/밤 상태를 전환하며 BFS를 진행하고, 목표 좌표에 도착하면 이동 거리를 반환한다. 도달하지 못하면 -1을 출력한다.