BFS (1) - 미로 탈출

문제

1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다. 미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.

 

제한사항 5 ≤ maps의 길이 ≤ 100 5 ≤ maps[i]의 길이 ≤ 100 maps[i]는 다음 5개의 문자들로만 이루어져 있습니다. S : 시작 지점 E : 출구 L : 레버 O : 통로 X : 벽 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다. 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

 

해석

배열로 된 미로를 최단 시간으로 빠져나가는 문제이다. 중요한 점은,

1. 레버를 당겨야 출구가 열린다.

2. 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있다.

3. 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있다.

 

BFS를 이용하여 풀기로 하였고, 시작 지점부터 레버까지의 최단 시간 + 레버에서 출구까지의 최단 시간을 구하면 정답이 될 것이다.

 

 

에러 핸들링

1. 큐를 이용하는 BFS는 매번 큐의 크기가 가변적으로 변하므로, 그 크기에 맞추어 반복문을 돌려주어야 하는데, 실수로 그 부분을 빼먹어서, 매 초 모든 경우의 수를 돌도록 만들어 버렸다. 

 

2. 전역 배열을 사용할 때, 원본 배열을 건들 경우 한 번 다시 초기화 해주는 습관을 길러야 할 것 같다.

 

3. 다른 경우의 수 중에서 더 짧은 시간이 나올 수 있다고 생각하여 Math.min함수를 통해 최솟값을 갱신해 주었는데, 생각해보니 시간 별로 체크하는 것이기 때문에 그럴 필요 없이 return 해버리면 된다는 것을 놓쳤다.

 

 

코드

import javafx.util.Pair;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.Arrays;


class Solution {
    
    static String[][] mapArr;
    static Boolean[][] visited;

    public static int solution(String[] maps) {
        int answer = 0;
        int[] s = new int[2];
        int[] l = new int[2];
        mapArr = new String[maps.length][];
        visited = new Boolean[maps.length][];
        for (int i = 0; i < mapArr.length; i++) {
            mapArr[i] = maps[i].split("");
            visited[i] = new Boolean[maps[i].length()];
            if (maps[i].contains("S")) {
                s[0] = i;
                s[1] = maps[i].indexOf("S");
            }
            if (maps[i].contains("L")) {
                l[0] = i;
                l[1] = maps[i].indexOf("L");
            }
        }

        for (Boolean[] row : visited) {
            Arrays.fill(row, false);
        }

        int stol = bfs(s, "L", visited);
        if (stol == Integer.MAX_VALUE) {
            answer = -1;
            return answer;
        }

        for (Boolean[] row : visited) {
            Arrays.fill(row, false);
        }

        int ltoe = bfs(l, "E", visited);
        if (ltoe == Integer.MAX_VALUE) {
            answer = -1;
            return answer;
        }

        answer = stol + ltoe;
        return answer;
    }

    static int bfs(int[] start, String end, Boolean[][] visited) {
        ArrayDeque<Pair<Integer, Integer>> q = new ArrayDeque<>();
        int second = 0;
        int[] ud = {0, 0, 1, -1};
        int[] lr = {-1, 1, 0, 0};

        q.offer(new Pair<>(start[0], start[1]));
        visited[start[0]][start[1]] = true;

        while (!q.isEmpty()) {
            int size = q.size();

            for (int s = 0; s < size; s++) {
                Pair<Integer, Integer> index = q.poll();
                int ci = index.getKey();
                int cj = index.getValue();

                for (int i = 0; i < 4; i++) {
                    int di = ci + ud[i];
                    int dj = cj + lr[i];

                    if (di >= 0 && di < mapArr.length && dj >= 0 && dj < mapArr[0].length) {
                        if ((mapArr[di][dj].equals("O") || mapArr[di][dj].equals("S") || mapArr[di][dj].equals("E")|| mapArr[di][dj].equals(end)) && !visited[di][dj]) {
                            visited[di][dj] = true;
                            q.offer(new Pair<>(di, dj));

                            if (mapArr[di][dj].equals(end)) {
                                return second + 1;
                            }
                        }
                    }
                }
            }

            second++;
        }
        return Integer.MAX_VALUE;
    }


}