© 2025 anveloper.dev
GitHub·LinkedIn·Contact

목차

  • 문제
  • 입력
  • 출력
  • 예제
  • 풀이
  • 코드
  • 복잡도
풀이 목록으로 돌아가기

BOJ 14442 - 벽 부수고 이동하기 2

2023-02-02
BOJ
골드 III
java
원본 문제 보기
그래프 이론
그래프 탐색
너비 우선 탐색
격자 그래프

문제

BOJ 14442 - 벽 부수고 이동하기 2

N×M 크기의 맵이 있다. 각 칸은 통로(0) 또는 벽(1)이다. (1,1)에서 (N,M)까지 이동하려 할 때, 최대 K개의 벽을 부수고 이동할 수 있다. 이동은 상하좌우 4방향으로 가능하며, 최단 경로를 구한다.

입력

첫째 줄에 N, M, K(1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ 10)가 주어진다. 다음 N개의 줄에 M개의 숫자(0 또는 1)로 이루어진 맵이 주어진다.

출력

최단 거리를 출력한다. 도달할 수 없으면 -1을 출력한다.

예제

입력

6 4 1
0100
1110
1000
0000
0111
0000

출력

15

풀이

핵심 아이디어: 3차원 방문 배열 visited[N][M][K+1]을 사용한다. 세 번째 차원은 지금까지 부순 벽의 수를 의미한다. 같은 위치라도 남은 벽 부수기 횟수가 다르면 다른 상태로 간주한다.

  1. BFS 큐에 {행, 열, 부순 벽 수, 현재 거리} 형태의 상태를 저장한다.
  2. 초기 상태 (0, 0, 0, 1)을 큐에 넣는다.
  3. 인접 칸으로 이동 시:
    • 인접 칸이 통로(0)이고, visited[nr][nc][k]가 미방문이면 같은 k로 이동한다.
    • 인접 칸이 벽(1)이고, k < K이며 visited[nr][nc][k+1]이 미방문이면 벽을 부수고 k+1로 이동한다.
  4. (N-1, M-1)에 도달하면 현재 거리를 반환한다.

3차원 방문 배열로 중복 탐색을 제거하므로, 시간 복잡도는 O(N·M·K)이다.

코드

import java.io.*;
import java.util.*;
 
public class Day369BOJ14442벽부수고이동하기2 {
    static int N, M, K;
    static int[] dr = { -1, 1, 0, 0 }, dc = { 0, 0, -1, 1 };
    static int[][] map;
    static Queue<int[]> q;
    static boolean[][][] visited;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
 
        map = new int[N][M];
 
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++)
                map[i][j] = str.charAt(j) - '0';
        }
 
        System.out.println(bfs());
        br.close();
    }
 
    private static int bfs() {
        q = new LinkedList<>();
        visited = new boolean[N][M][K + 1];
 
        visited[0][0][0] = true;
        q.add(new int[] { 0, 0, 0, 1 });
 
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int r = cur[0], c = cur[1], k = cur[2], d = cur[3];
 
            if (r == N - 1 && c == M - 1)
                return d;
 
            for (int dir = 0; dir < 4; dir++) {
                int nr = r + dr[dir];
                int nc = c + dc[dir];
 
                if (index(nr, nc))
                    continue;
 
                if (map[nr][nc] == 0 && !visited[nr][nc][k]) {
                    visited[nr][nc][k] = true;
                    q.add(new int[] { nr, nc, k, d + 1 });
                } else if (k < K && !visited[nr][nc][k + 1]) {
                    visited[nr][nc][k + 1] = true;
                    q.add(new int[] { nr, nc, k + 1, d + 1 });
                }
            }
        }
        return -1;
    }
 
    private static boolean index(int nr, int nc) {
        return nr < 0 || nr >= N || nc < 0 || nc >= M;
    }
}

복잡도

  • 시간: O(N·M·K) — 각 셀을 K+1가지 상태로 한 번씩 방문
  • 공간: O(N·M·K) — 3차원 방문 배열