[BOJ] 백준 [14442] 벽 부수고 이동하기 2JAVA

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

14442번: 벽 부수고 이동하기 2

[문제]

[풀이]

기본적으로 좌표 Map 에서 BFS를 시행하면 최단경로로 가기때문에 다익스트라랑 유사한 알고리즘으로 동작한다.

일반적인 BFS로 풀이하되 벽을 부수는 경우가 추가로 생겼기 때문에 이에 대한 check를 나타내야함
visit 방문확인 배열을 3차원으로 하여 크기는 k+1로 둔다. (벽을 안 부쉬는 경우도 있기 때문)

벽을 부술때마다 +1 씩하여 다른 visit 배열을 체크하도록 하면 되는데

그냥 이렇게만 하면 큐 뻥이 나버린다
그래서 한번 방문 했던 곳은 무시하도록 추가적으로 조취를 취해 주면 가장 먼저 종결조건에 다다르는 노드가
제일 최단거리로 도착한 노드이므로 종료

 

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

import static java.util.Arrays.*;
import static java.util.stream.Collectors.*;
import static java.util.stream.IntStream.*;

public class Main {

    static int w,h,k;
    static boolean[][][] visit;
    static int[][] map;
    static int[] dx = {0,1,0,-1},dy = {1,0,-1,0};

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 초기 입력값 세팅
        int[] input = stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();
        w = input[1]; h = input[0]; k = input[2];
        visit = new boolean[h][w][k+1];
        map = new int[h][w];

        for(int i=0;i<h;i++)
            map[i] = stream(br.readLine().split(""))
                    .mapToInt(Integer::parseInt).toArray();

        System.out.println(bfs(new Node(0,0,1,0)));
    }
    static int bfs(Node node){

        Queue<Node> q = new LinkedList<Node>();
        q.add(node);

        while (!q.isEmpty()){
            Node cur = q.poll();

            if(visit[cur.y][cur.x][cur.breakCount])
                continue;
            visit[cur.y][cur.x][cur.breakCount]=true;

            // 종결 조건
            if(cur.x==w-1 && cur.y==h-1)
                return cur.depth;

            for(int i=0;i<dx.length;i++){

                int nextX = cur.x+dx[i];
                int nextY = cur.y+dy[i];

                if(!isRange(nextX,nextY)) continue;

                if(map[nextY][nextX]==0 && !visit[nextY][nextX][cur.breakCount])
                    q.add(new Node(nextX,nextY,cur.depth+1,cur.breakCount));
                else if(cur.breakCount<k && !visit[nextY][nextX][cur.breakCount+1]) // 벽 부쉴때
                    q.add(new Node(nextX,nextY,cur.depth+1,cur.breakCount+1));

            }
        }
        return -1;
    }
    static class Node{
        int x,y,depth,breakCount;

        public Node(int x, int y, int depth, int breakCount) {
            this.x = x;
            this.y = y;
            this.depth = depth;
            this.breakCount = breakCount;
        }
    }
    static boolean isRange(int x,int y){
        return x>=0&&y>=0&&x<w&&y<h;
    }


}