[LeetCode] 864 - Shortest Path to Get All Keys(java)

https://leetcode.com/problems/shortest-path-to-get-all-keys/

Shortest Path to Get All Keys - LeetCode

친구의 추천으로 리트코드 문제를 처음 풀어보았다. 해당 문제는 이틀 전인가 데일리 문제로 나왔던 문제이다.

어쩌다 보니 처음부터 hard 난이도를 풀었는데 생각보다 재미있었던 것 같다.

아무튼 풀이를 하자면 아래와 같다.

(단순히 문제를 푸는 것에 집중하여 하드코딩하였다. 리펙은 진행하지 않았기에 코드를 이해하기 어려울 수 있다. 흐름만 봐도 이해할 수 있긴 할 것이다.)

 

 

핵심

자물쇠는 키가 있어야지만 이동할 수 있다. 흔히 사용하는 bfs에서 키를 가지게 되면 뒤로 돌아가는 방법이 더 빨라질 수 있다.

이러한 개념을 가지고 가야 한다. 또한 중요한 것은 키를 가진 상태를 나타내야 하는데 이를 나타내기 위해 이진법을 사용하였다.

예를 들면 abcdef키가 있고 모두 가지고 있다면 111111(2)이고, 만약 f만 가지고 있다면 000001(2)이 된다. 즉 총경우의 수는 

2^키의 개수이다.

 

정답 코드

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

class Solution {
    private char[][] map;
    private int max;
    private final int[] dy = {1, 0, -1, 0};
    private final int[] dx = {0, -1, 0, 1};
    private final Set<Character> keys = new HashSet<>();

    public int shortestPathAllKeys(String[] grid) {
        map = new char[grid.length][grid[0].length()];
        int startY = 0;
        int startX = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length(); j++) {
                map[i][j] = grid[i].charAt(j);
                if (map[i][j] != '@' && map[i][j] != '.' && map[i][j] != '#') {
                    keys.add((map[i][j] + "").toLowerCase().charAt(0));
                }
                if (map[i][j] == '@') {
                    startY = i;
                    startX = j;
                }
            }
        }
        max = (int) Math.pow(2, keys.size()) - 1;

        return bfs(startY, startX, keys.size());
    }

    private int bfs(int y, int x, int keysSize) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{y, x, 0});
        int[][][] dis = new int[map.length][map[0].length][(int) Math.pow(2, keysSize)];
        dis[y][x][0] = 1;

        while (!q.isEmpty()) {
            int[] now = q.poll();

            if (now[2] == max) {
                return dis[now[0]][now[1]][max] - 1;
            }

            for (int i = 0; i < 4; i++) {
                int moveY = now[0] + dy[i];
                int moveX = now[1] + dx[i];
                int keyStatus = now[2];
                String key = Integer.toBinaryString(keyStatus);
                int count = keysSize - key.length();
                key = "0".repeat(count) + key;

                if (0 <= moveY && moveY < map.length && 0 <= moveX && moveX < map[0].length) {
                    if (map[moveY][moveX] == '#') {
                        continue;
                    }

                    for (int j = 0; j < keysSize; j++) {
                        if (dis[moveY][moveX][keyStatus] == 0) {

                            if (map[moveY][moveX] == 'A' + j) {
                                if (key.charAt(j) == '0') {
                                    break;
                                }
                                dis[moveY][moveX][keyStatus] = dis[now[0]][now[1]][keyStatus] + 1;
                                q.offer(new int[]{moveY, moveX, keyStatus});
                                break;
                            }

                            if (map[moveY][moveX] == 'a' + j) {

                                int nextKeyStatus = keyStatus;
                                if (key.charAt(j) == '0') {
                                    nextKeyStatus = (keyStatus + (int) Math.pow(2, keysSize - j - 1));
                                }

                                dis[moveY][moveX][nextKeyStatus] =
                                        dis[now[0]][now[1]][keyStatus] + 1;
                                q.offer(new int[]{moveY, moveX, nextKeyStatus});
                                break;
                            }
                            if (map[moveY][moveX] == '.' || map[moveY][moveX] == '@') {
                                q.offer(new int[]{moveY, moveX, keyStatus});
                                dis[moveY][moveX][keyStatus] = dis[now[0]][now[1]][keyStatus] + 1;
                                break;
                            }
                        }
                    }
                }
            }
        }
        return -1;
    }
}

해설

시작점을 알아야 한다. 또한 string [] 이거 단독으로 컨트롤하기 힘들어서 2차원 배열로 만들면서 시작점 찾았다.

추가로 키값이 1~6이다. 따라서 키의 수도 따로 찾아준다.

이제 중요한데 bfs 돌릴 때 키를 획득하면 새로운 공간에서 다시 시작한다고 생각해야 함 -> 즉 다른 배열값으로 이동해야 한다.

이유는 획득 시에 뒤로 돌아가야 할 경우가 생기기 때문에 맵을 새로운 곳에서 다시 시작한다고 생각하면 된다.

키는 획득한 채로 근데 중요한 게 이 키를 갖고 있다는 걸 알고 있어야 함 각 맵마다 비트연산을 사용 즉 6 자리면 111111이라면 abcdef를 다 먹은 경우는 000001이면 f만 먹고 새로운 배열에서 탐색이라 생각하면 된다.

그래서 3차원배열 뒤에가 2^키개수가 된다.

 

이제는 단순 이동인데 자물쇠일 때 키가 있는지 보고 없으면 돌아가고 첨에 0을 2진수로 하면 0이라서 앞에 0을 붙이기 위해서 repeat로 사용했다. 이제 움직임을 검증할 때 단순하게 생각하면 bfs고 열쇠를 받으면 새로운 공간으로 가기 때문에 처음 방문한 곳만 가면 된다. -> map이 0인곳 그래서 처음 위치를 1로 설정한 이유도 이러한 이유 때문이다.

 

자물쇠일 때는 키가 있는지 확인해야 한다. 키는 아까말했듯이 2진수로 나타낸값의 index가 1 인지확인 없으면 이동불가이고 있으면 다음 위치를 큐에 넣어준다. 만약 열쇠라면 다시 조건이 있다. 이 열쇠를 한 번도 안 먹은 경우와 먹은 적이 있는 경우를 확인해야 한다. 이 부분도 2진수로 해당 위치의 키가 있는지 확인한다.  그리고 처음 먹었으면 다른 맵을 큐에 넣는다. 마지막으로 그냥 아무것도 아닌 경우에는 그냥 전에 있던 위치에서 1을 더 해주면 된다.

 

 

배운 점

이 문제를 푸는데 2시간 정도 걸린 것 같다. 처음 보자마자 들었던 생각은 다른 차원이동을 배열로 해야 하는데, 8차 배열을 쓸까 생각도 했지만 당연히 잘못되었다는 것을 판단하고 이를 고민했었다. 곰곰이 생각하다 각 키를 가진 것을 이진법을 통해 나타내면 좋을 것 같다는 생각을 하고 이를 적용해 보았다. 결론적으로는 잘 풀기는 하였지만, 코드를 작성하는데 하드코딩을 하게 되어 디버깅에 어려움을 겪었다.

문제를 푸는 것도 중요하지만 알고리즘이라도 메서드 분리를 통해 디버깅도 생각하며 코딩을 해야겠다.