[백준] 14442 - 벽 부수고 이동하기 2 (Java)

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

 

자바로 한번 구현해봤더니 파이썬의 편리함을 다시 한번 깨닫게 해준 문제...

 

문제 풀이는 간단하다.

(i, j) 위치에 k번의 벽 부수기 횟수가 남은 상태로 도착했을 때, 그때의 최단 이동 경로를 다 저장하면된다.

최악의 경우 1000*1000*10 = 1000만 칸의 배열을 채워야 하는데, 2초 시간 제한과 512MB 의 메모리 제한이라면 충분히 채울 수 있다.

 

만약 이동하려는 칸이 벽이라면 현재 칸에서 남은 벽 부수기 횟수를 1 감소시켜서 이동시키고, 이동하려는 칸이 벽이 아니라면 남은 횟수를 그대로 가져가면서 이동하면 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int[][] board;
    static boolean[][][] visited;
    static int[][][] dp;

    static Queue<List<Integer>> q = new LinkedList<>();

    static int INF = Integer.MAX_VALUE;

    static int[] di = {0, 0, 1, -1};
    static int[] dj = {1, -1, 0, 0};

    static int EMPTY = 0;
    static int WALL = 1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        board = new int[n][m];
        dp = new int[n][m][k+1];
        visited = new boolean[n][m][k+1];

        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < m; j++) {
                board[i][j] = line.charAt(j) - '0';
                Arrays.fill(dp[i][j], INF);
            }
        }

        q.add(List.of(0, 0, k));
        visited[0][0][k] = true;
        dp[0][0][k] = 1;
        while (!q.isEmpty()) {
            List<Integer> cur = q.poll();
            int now_i = cur.get(0);
            int now_j = cur.get(1);
            int now_k = cur.get(2);

            for (int l = 0; l < 4; l++) {
                int next_i = now_i + di[l];
                int next_j = now_j + dj[l];
                if (0 <= next_i && next_i < n && 0 <= next_j && next_j < m) {
                    if (board[next_i][next_j] == WALL && now_k > 0) {
                        if (!visited[next_i][next_j][now_k-1]) {
                            visited[next_i][next_j][now_k-1] = true;
                            q.add(List.of(next_i, next_j, now_k-1));
                            dp[next_i][next_j][now_k-1] = dp[now_i][now_j][now_k] + 1;
                        }
                    }
                    if (board[next_i][next_j] == EMPTY) {
                        if (!visited[next_i][next_j][now_k]) {
                            visited[next_i][next_j][now_k] = true;
                            q.add(List.of(next_i, next_j, now_k));
                            dp[next_i][next_j][now_k] = dp[now_i][now_j][now_k] + 1;
                        }
                    }
                }
            }
        }

        int ans = Arrays.stream(dp[n-1][m-1]).min().getAsInt();
        if (ans == INF) {
            System.out.println(-1);
        } else {
            System.out.println(ans);
        }
    }
}

 

< 이 문제를 풀면서 알게 된 점 >

 

1. 다른 사람의 풀이를 봤을 때 큐에 들어가는 데이터를 List 가 아니라 별도의 클래스로 만들어서 넘겼다. 그것도 괜찮은 풀이라는 생각이 들었다. 마치 C++ 에서 구조체를 쓰는 느낌과 비슷한 것 같다.

 

2. List.of 라는 메서드는 Java 8 에서는 컴파일 에러가 난다. Java 11 로 제출했더니 맞았다.