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

1. 문제 링크

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

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

 

2. 접근법

일반적인 bfs와 다른 것은 벽을 부술 수 있다는 것

그렇다면 어디를 부쉈는지에 따라 visited 배열이 달라질 것이다.

부술 수 있는 최대 벽의 수 k는 1부터 10까지이므로, visited를 3차원 배열로 선언하여 k에 따른 방문 여부를 저장한다.

 

visited[][][]를 3차원으로 선언한 것 외에는 특별한 점 없음

 

3. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// 벽 부수고 이동하기 2

public class BJ14442 {

    private static class Node {
        int x;
        int y;
        int distance;
        int destroyed;

         Node(int x, int y, int distance, int destroyed) {
            this.x = x;
            this.y = y;
            this.distance = distance;
            this.destroyed = destroyed;
         }
    }
    static int n, m;
    static int k;
    static int ans = Integer.MAX_VALUE;
    static boolean[][] board;
    static boolean[][][] visited;           // visited[k][n][m] 벽은 부순 횟수 k에 따라 방문 여부 체크
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static Queue<Node> queue = new LinkedList<>();

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

        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());
        
        board = new boolean[n + 1][m + 1];
        visited = new boolean[k+1][n + 1][m + 1];

        for(int i = 1; i <= n; i++) {
            String line = br.readLine();
            for(int j = 0; j < m; j++) {
                if(line.charAt(j) == '1') {
                    board[i][j + 1] = true;
                }
            }
        }

        solution();

        if(ans == Integer.MAX_VALUE) ans = -1;
        System.out.println(ans);
    }

    private static void solution() {

        visited[0][1][1] = true;
        queue.add(new Node(1, 1, 1, 0));
    
        while(!queue.isEmpty()) {

            Node poll = queue.poll();

            if(poll.x == n && poll.y == m) {
                ans = Integer.min(ans, poll.distance);
                return;
            }
            
            for(int i = 0; i < 4; i++) {
                int xx = poll.x + dx[i];
                int yy = poll.y + dy[i];

                if(xx < 1 || xx > n || yy < 1 || yy > m) continue;
                if(visited[poll.destroyed][xx][yy]) continue;

                if(!board[xx][yy]) {        // 벽이 없는 경우
                    visited[poll.destroyed][xx][yy] = true;
                    queue.add(new Node(xx, yy, poll.distance + 1, poll.destroyed));
                }
                else {                      // 벽이 있는 경우
                    if(poll.destroyed < k) {
                        visited[poll.destroyed][xx][yy] = true;
                        queue.add(new Node(xx, yy, poll.distance + 1, poll.destroyed + 1));
                    }
                }
            }
        }
    }
    
}

 

4. 막힌 부분

정답 풀이와는 완전 다르게 접근했었다.

visited 배열을 만들지 않고, dp 배열을 만들어 [0][x][y]에는 distance 값, [1][x][y]에는 destroyed 값을 저장했다.

물론 Node 클래스도 동일하게 사용하여 distance 값과 destroyed 값을 또 저장했다. (비효율적임)

 

왜 이렇게 했었을까?

 

최소 distance 값을 구하는 것이 목표였기에

x, y 위치에 따라 distance 값을 저장하여,

이동할 위치의 distance < 원래 위치의 distance 인 경우에만 탐색을 하려고 했었다.

 더불어 destroyed 값도 고려하여,

destroyed 값이 작은 경로에 우선순위를 주도록 했다.

 

그런데 이렇게 하다보니 다음과 같은 문제점이 생겼다.

(1) 논리적 오류

destroyed 값이 작다고 무조건 우선순위가 높은 것은 아님

→ 어찌저찌 해결..

 

(2) 복잡한 로직

케이스가 여러 개로 나뉘어 풀이가 너무 더러워짐

→ (1)을 해결하려다 보니..

 

(3) 메모리 초과

여러 테케 잘 돌아갔지만 결국 메모리 초과 발생..

 

분명 더 효율적인 방법이 있을 거 같아서 다른 분들의 풀이를 참고했다.

k의 최댓값이 크지 않기에 visited 배열을 사용해서 아예 나누어 버리면 깔끔하게 해결할 수 있었다.