[백준] 9328번 열쇠(java)

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

9328번: 열쇠

이번에도 bfs 문제이다. 

이와 비슷한 문제를 리트 코드에서도 풀었던 기억이 있는데, 그에 비하면 쉽다고 생각한다.

이유는 최단 거리를 찾는 문제는 아니기에 정보를 공유할 수 있기 때문이다. 

 

 

핵심

우선 최단거리를 찾는 문제가 아니라 찾을 수 있는 열쇠의 수를 찾는 것이다.

이전에 bfs 특성상 어떤 열쇠를 먼저 먹고, 어떤 식으로 이동해야 가장 빠르게 도달할 수 있는지를 찾는 문제라면 복잡해질 수 있다.(아래링크)

https://kimtaesoo99.tistory.com/224

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

위의 문제의 경우에는 각각의 열쇠를 먹을 때의 정보가 전부 다르다. -> 최단 거리를 찾아야 하므로 정보를 각각 가지고 있어야 함(어떤 열쇠를 먹었고 어떤 문을 열었는지.. 등등)

하지만 이것은 어떤 식으로든지 단순히 최대한 많이 문서를 찾는 것이 목적이기에 만약 문을 열거나, 열쇠를 찾을 경우 그 정보를 계속 공유할 수 있다.

 

정답 코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int result = 0;
    static int[][] move = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

        for (int test = 0; test < t; test++) {
            result = 0;
            int h = sc.nextInt();
            int w = sc.nextInt();
            String[][] map = new String[h + 2][w + 2];

            for (int i = 1; i < h + 1; i++) {
                String info = sc.next();
                for (int j = 1; j < w + 1; j++) {
                    map[i][j] = info.split("")[j - 1];
                }
            }

            for (int i = 0; i < w + 2; i++) {
                map[0][i] = ".";
                map[h + 1][i] = ".";
            }

            for (int i = 0; i < h + 2; i++) {
                map[i][0] = ".";
                map[i][w + 1] = ".";
            }

            String keys = sc.next();

            List<String> key = new ArrayList<>();
            if (!keys.equals("0")) {
                for (int i = 0; i < keys.length(); i++) {
                    key.add(String.valueOf(keys.charAt(i)));
                }
            }
            bfs(map, key);
            System.out.println(result);
        }
    }

    private static void bfs(String[][] map, List<String> key) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0, 0});
        boolean[][] visited = new boolean[map.length][map[0].length];

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

            for (int i = 0; i < 4; i++) {
                int moveY = location[0] + move[i][0];
                int moveX = location[1] + move[i][1];

                if (0 <= moveY && moveY < map.length && 0 <= moveX && moveX < map[0].length) {
                    if (!map[moveY][moveX].equals("*") && !visited[moveY][moveX]) {
                        if (map[moveY][moveX].equals("$")) {
                            result++;
                        } else if (Character.isLowerCase(map[moveY][moveX].charAt(0))) { //열쇠
                            key.add(map[moveY][moveX]);
                            visited = new boolean[map.length][map[0].length];
                        } else if (Character.isUpperCase(map[moveY][moveX].charAt(0))) {  // 문
                            String door = map[moveY][moveX].toLowerCase();
                            if (!key.contains(door)) {
                                continue;
                            }
                        }
                        map[moveY][moveX] = ".";
                        q.offer(new int[]{moveY, moveX});
                        visited[moveY][moveX] = true;
                    }
                }
            }
        }
    }
}

해설

맵을 초기화하는 과정이 조금은 복잡하다.

건물의 바깥은 전부 지나갈 수 있는 "."으로 초기화해 주었다.

이제 이후 [0,0]에서 부터 시작하여 bfs를 시도한다.

이 문제가 재미있는 것은 bfs를 사용하지만 최단거리를 찾는 것이 목표가 아니기에 정보를 공유할 수 있다.

즉 이동했을 때 문을 열 수 있다면 그 문을 열고 "."으로 바꾸어주어 언제든지 이동가능하게 해 준다

또한 문서를 획득했을 때도 단순하게 result++를 해주고 이동할 수 있는 길(".")로 바꾸어준다

가장 중요한 부분은 열쇠를 새롭게 획득했을 때이다.

무한 루프를 방지하기 위해 여태까지 걸어온 길은 다시 돌아가지 않는다.

하지만 새로운 열쇠를 획득했을 경우 이전으로 돌아가 다시 문을 열 수 있기에 visited를 초기화해 준다.

 

 

배운 점

내 생각에 예전에 풀어본 리트 코드문제가 훨씬 어렵다고 느껴진다.

처음 문제를 봤을 때 리트 코드에서 푼 문제와 동일하다 생각하였는데, 

이를 논리적으로 생각해 보니 정보를 공유할 수 있다는 사실을 하고 매우 쉽게 풀 수 있었다.

확실히 문제를 많이 풀 수록 논리적인 사고력이 늘고 있다고 느껴진다.