[알고리즘] 백준 > #2206. 벽 부수고 이동하기

문제링크

백준 #2206. 벽 부수고 이동하기

풀이방법

신기한 문제다! 벽을 한 번만 부술 수 있는데 이걸 어디에 어떻게 설정해서 알 수 있을까 생각했다. 보통 이차원 배열을 맵으로 사용하는데, 여기서는 한 차원을 더 뒀다. 삼차원 배열을 사용했다. [0][i][j]는 한 번도 벽을 부수지 않은 케이스를 다루고 [1][i][j]는 벽을 한 번 부순 상태를 다룬다. [i][j]에서 벽이 있는 곳을 마주하면 z값이 0인지 확인한다. 0이면 z를 1로 설정해 최소 값으로 해당 위치에 도달할 수 있는지 확인하는 방식이다. z가 1이면 이미 한 번 벽을 부쉈기 때문에 어떤것도 하지 않는다!

코드

class Solution2206 {

    private final int[] dy = {0, 0, +1, -1};
    private final int[] dx = {+1, -1, 0, 0};

    private final int NOT_VISITED = 10000000;

    private int n, m;
    private int[][] map;


    Solution2206(int n, int m, int[][] map) {
        this.n = n;
        this.m = m;

        this.map = new int[n][m];
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) this.map[i][j] = map[i][j];
    }

    int searchShortestPath() {
        int[][][] count = new int[2][n][m];
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
            count[0][i][j] = NOT_VISITED;
            count[1][i][j] = NOT_VISITED;
        }

        Queue<Triple> q = new LinkedList<>();
        q.offer(new Triple(0, 0, 0));
        count[0][0][0] = 1;

        while (!q.isEmpty()) {
            Triple head = q.poll();
            for (int d = 0; d < 4; d++) {
                int nextY = head.y + dy[d];
                int nextX = head.x + dx[d];

                if (!isInRange(nextY, nextX)) continue;

                int nextZ;
                if (map[nextY][nextX] == 0) nextZ = head.z;
                else if (head.z == 0) nextZ = 1;
                else continue;

                if (count[nextZ][nextY][nextX] > (count[head.z][head.y][head.x] + 1)) {
                    count[nextZ][nextY][nextX] = count[head.z][head.y][head.x] + 1;
                    q.offer(new Triple(nextZ, nextY, nextX));
                }
            }
        }

        int shortestPath = Math.min(count[0][n - 1][m - 1], count[1][n - 1][m - 1]);
        return shortestPath != NOT_VISITED ? shortestPath : -1;
    }

    private boolean isInRange(int y, int x) {
        return ((y >= 0) && (y < n) && (x >= 0) && (x < m));
    }
}

class Triple {

    int z, y, x;

    Triple(int z, int y, int x) {
        this.z = z;
        this.y = y;
        this.x = x;
    }
}