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

문제 링크

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

풀이 과정

(0,0)에서 (N-1, M-1)로 벽을 K개만큼 부수고 이동할 수 있는 BFS 탐색 문제입니다.

visit = new boolean[N][M][K + 1];

각 좌표로 이동시에 벽을 몇 개 부수고 도착했는지를 판단하기 위해 3차원의 visit 배열이 사용되었습니다.

if (map[nx][ny] == 0 && !visit[nx][ny][now.cnt]) {
    visit[nx][ny][now.cnt] = true;
    queue.add(new Point(nx, ny, now.dist + 1, now.cnt));
}

if (map[nx][ny] == 1 && now.cnt + 1 <= K && !visit[nx][ny][now.cnt + 1]) {
    visit[nx][ny][now.cnt + 1] = true;
    queue.add(new Point(nx, ny, now.dist + 1, now.cnt + 1));
}

인접 좌표가 빈 공간이라, 벽을 부수지 않고 이동할 수 있는 경우와 인접 좌표가 벽이라 벽을 부수고 이동할 수 있는 경우를 나누어 판단합니다.

• 빈 공간인 경우는, 현재까지 벽을 몇 개 부쉈는지를 담고 있는 cnt 변수의 값을 가져와, 그 값 그대로 이용해 방문 여부를 체크합니다. 이 조건에 부합하면 큐에 넣고 방문처리합니다.
• 벽인 경우, 먼저 벽을 부수는 횟수가 남아있는지를 확인하고, 벽 부순 개수를 1 증가시킨 횟수로 해당 좌표에 방문한 적이 있는지를 체크합니다. 이 조건에 부합하면 큐에 넣고 방문처리합니다.

  if (now.x == N - 1 && now.y == M - 1) {
      answer = now.dist;
      break;
  }

종점에 도착한다면 현재까지 지나온 칸의 개수를 변수에 담습니다. 도착하지 못한다면, 기존 변수 값 -1을 출력합니다.

코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N, M, K;
    static int[][] map;
    static boolean[][][] visit;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int answer = -1;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        K = sc.nextInt();
        map = new int[N][M];
        visit = new boolean[N][M][K + 1];

        for (int i = 0; i < N; i++) {
            String s = sc.next();
            for (int j = 0; j < M; j++) {
                map[i][j] = s.charAt(j) - '0';
            }
        }

        Queue<Point> queue = new LinkedList<>();
        visit[0][0][0] = true;
        queue.add(new Point(0, 0, 1, 0));

        while (!queue.isEmpty()) {
            Point now = queue.poll();

            if (now.x == N - 1 && now.y == M - 1) {
                answer = now.dist;
                break;
            }

            for (int d = 0; d < 4; d++) {
                int nx = now.x + dx[d];
                int ny = now.y + dy[d];

                if (!inRange(nx, ny)) continue;

                if (map[nx][ny] == 0 && !visit[nx][ny][now.cnt]) {
                    visit[nx][ny][now.cnt] = true;
                    queue.add(new Point(nx, ny, now.dist + 1, now.cnt));
                }

                if (map[nx][ny] == 1 && now.cnt + 1 <= K && !visit[nx][ny][now.cnt + 1]) {
                    visit[nx][ny][now.cnt + 1] = true;
                    queue.add(new Point(nx, ny, now.dist + 1, now.cnt + 1));
                }
            }
        }

        System.out.println(answer);
    }

    static boolean inRange(int x, int y) {
        if (x < 0 || x > N - 1 || y < 0 || y > M - 1) return false;
        return true;
    }

    static class Point {
        int x, y, dist, cnt;

        public Point(int x, int y, int dist, int cnt) {
            this.x = x;
            this.y = y;
            this.dist = dist;
            this.cnt = cnt;
        }
    }
}