[BaekJoon] 14442 벽 부수고 이동하기 2 (Java)

1.  문제 링크

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

2.  문제

요약

• N x M의 행렬로 표현되는 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타냅니다.
• (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 최단 경로로 이동하려고 합니다.
• 최단경로에는 시작하는 칸과 끝나는 칸도 포함해서 셉니다.
• 만약 이동하는 도중에 벽을 부수고 이동하는 것이 경로가 더 짧아진다면 벽을 K개까지 부수고 이동하여도 됩니다.
• 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸입니다.
• 맵이 주어졌을 때, 최단 경로를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1,000보다 작거나 같은 N과 M, 1보다 크거나 같고 10보다 작거나 같은 K가 주어지고 두 번째 줄부터 N개의 줄에 M개의 숫자로 맵이 주어집니다. (1, 1)과 (N, M)은 항상 0이라고 가정합니다.
• 출력: 첫 번째 줄에 최단거리를 출력합니다. 불가능할 때는 -1을 출력합니다.

3.  소스코드

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, M, K;
    static int[][] map;
    static void input() {
        Reader scanner = new Reader();
        N = scanner.nextInt();
        M = scanner.nextInt();
        K = scanner.nextInt();
        map = new int[N][M];
        for(int row = 0; row < N; row++) {
            String info = scanner.nextLine();
            for(int col = 0; col < M; col++) {
                map[row][col] = info.charAt(col) - '0';
            }
        }
    }

    static void solution() {
        int answer = bfs(new int[] {0, 0}, new int[] {N - 1, M - 1});
        System.out.println(answer == 0 ? -1 : answer);
    }

    static int bfs(int[] start, int[] end) {
        int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
        Queue<Loc> queue = new LinkedList<>();
        queue.offer(new Loc(start[0], start[1], 1, 0));
        boolean[][][] visited = new boolean[N][M][K + 1];
        visited[start[0]][start[1]][0] = true;
        int answer = 0;
        while(!queue.isEmpty()) {
            Loc cur = queue.poll();
            if(cur.x == end[0] && cur.y == end[1]) {
                answer = cur.space;
                break;
            }
            for(int dir = 0; dir < 4; dir++) {
                int cx = cur.x + dx[dir], cy = cur.y + dy[dir];
                if(isInMap(cx, cy)) {
                    if(map[cx][cy] == 0) {
                        if(!visited[cx][cy][cur.wall]) {
                            visited[cx][cy][cur.wall] = true;
                            queue.offer(new Loc(cx, cy, cur.space + 1, cur.wall));
                        }
                    } else if(map[cx][cy] == 1 && cur.wall < K) {
                        if(!visited[cx][cy][cur.wall + 1]) {
                            visited[cx][cy][cur.wall + 1] = true;
                            queue.offer(new Loc(cx, cy, cur.space + 1, cur.wall + 1));
                        }
                    }
                }
            }
        }
        return answer;
    }

    static boolean isInMap(int x, int y) {
        if(x >= 0 && x < N && y >= 0 && y < M) return true;
        return false;
    }

    static class Loc {
        int x, y, space, wall;
        public Loc(int x, int y, int space, int wall) {
            this.x = x;
            this.y = y;
            this.space = space;
            this.wall = wall;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

4.  접근

• 맵을 map이라는 2차원 배열에 저장하고 BFS를 통해 최단경로에서의 최단거리를 구합니다.
• 위치의 x, y 좌표와 현재까지 지난 위치들의 개수, 부순 벽의 개수를 멤버 변수로 가지는 Loc 클래스를 생성합니다.
• Queue와 3차원 배열 visited를 생성하는데, Queue는 탐색할 위치들을 담는 자료구조이고 visited는 각 위치를 방문했는지를 나타냅니다.
  • visited[x][y][k] = 벽을 k개 부셔서 (x, y) 위치를 방문했는지 여부
• Queue에 시작 위치인 (1, 1)을 Loc 객체로 만들어 넣고 시작 위치는 방문 체크를 합니다.
• Queue가 비워질 때까지 Queue에서 Loc 객체를 하나씩 꺼내서 (N, M) 위치까지 이동할 수 있는지, 이동할 수 있다면 최단거리가 얼마인지 구합니다.
  • Queue에서 Loc 객체를 하나 꺼내고 (N, M) 위치인지 확인하여 그렇다면 Queue에서 꺼낸 Loc 객체의 space 값, 즉 지금까지 지나온 위치들의 개수를 반환합니다.
  • 그렇지 않다면 현재 위치의 상하좌우 위치를 살펴 해당 위치가 맵 내부에 있는지 확인합니다.
  • 맵 내부에 있다면 아래 두 경우로 나누어 방문 체크를 하고 Queue에 다음에 탐색할 Loc 객체를 생성하여 넣습니다.
    • 만약 이동한 위치의 맵의 값이 0이라면 이동할 수 있는 칸이므로 지금까지 부순 벽의 개수에서 이동한 위치의 visited 값을 확인하고 아직 방문하지 않은 경우 방문 체크를 하고 Queue에 이동한 위치를 Loc 객체로 생성하여 넣습니다.
    • 만약 이동한 위치의 맵의 값이 1이라면 벽이므로 이동할 수 없는데, 만약 지금까지 부순 벽의 개수가 K개 미만이라면 해당 벽을 부수고 해당 위치로 이동할 수 있기 때문에 해당 벽까지 부순 후의 부순 벽의 개수에서 이동한 위치의 visited 값을 확인하고 아직 방문하지 않은 경우 방문 체크를 하고 Queue에 이동한 위치를 Loc 객체로 생성하여 넣습니다.
• Queue가 비워질 때까지 (N, M)에 도착할 수 없다면 (N, M)까지 도달할 수 없다는 뜻이므로 -1을 출력합니다.