프로그래머스 - 미로 탈출

프로그래머스 - 미로 탈출

시작점과 잠긴 출구, 그리고 출구를 열 수 있는 레버의 위치가 주어진 미로가 주어집니다. 미로는 벽과 통로로 구성돼있으며, 시작점, 출구, 레버, 통로를 원하는 만큼 지나갈 수 있습니다. 이 때 레버에 도달하여 출구를 열고 난 뒤 출구를 통해 미로를 빠져나가는 최소 시간을 구하는 문제입니다. 시작점부터 레버까지 BFS를 하고, 레버부터 출구까지 BFS를 하면 됩니다. 더 짧은 경로가 존재한다면 둘 중 한 파트가 더 짧다는건데 BFS로 찾은게 제일 짧을테니까 말이 안되죠.

import java.util.*;

class Solution {
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    
    public int solution(String[] maps) {
        int answer = 0;
        int[][] steps = new int[maps.length][maps[0].length()];
        int[][] copiedSteps = new int[maps.length][maps[0].length()];
        int[] start = new int[2];
        int[] lever = new int[2];
        int[] exit = new int[2];
        Queue<Integer> queue = new LinkedList<>();
        
        for (int i = 0; i < maps.length; i++) {
            for (int j = 0; j < maps[0].length(); j++) {
                String cur = maps[i].substring(j, j + 1);                
                if (cur.equals("X")) {
                    steps[i][j] = -1;
                    copiedSteps[i][j] = -1;
                }
                if (cur.equals("S")) {
                    start = new int[] {i, j};
                }
                if (cur.equals("L")) {
                    lever = new int[] {i, j};
                }
                if (cur.equals("E")) {
                    exit = new int[] {i, j};
                }
            }
        }
        
        bfs(queue, steps, start, lever);
        if (steps[lever[0]][lever[1]] == -2) {
            return -1;
        }
        answer += steps[lever[0]][lever[1]];
        
        queue = new LinkedList<>();
        bfs(queue, copiedSteps, lever, exit);
        if (copiedSteps[exit[0]][exit[1]] == -2) {
            return -1;
        }
        answer += copiedSteps[exit[0]][exit[1]];
        
        return answer;
    }
    
    public void bfs(Queue<Integer> queue, int[][] steps, int[] from, int[] to) {
        queue.add(1000 * from[0] + from[1]);
        steps[from[0]][from[1]] = 1;
        steps[to[0]][to[1]] = -2;
        
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            int x = cur / 1000;
            int y = cur % 1000;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if (nx >= 0 && nx < steps.length && ny >= 0 && ny < steps[0].length
                        && steps[nx][ny] != -1 && steps[nx][ny] <= 0) {
                
                    if (steps[nx][ny] == -2) {
                        steps[nx][ny] = steps[x][y];
                        return;
                    }
                    
                    steps[nx][ny] = steps[x][y] + 1;
                    queue.add(1000 * nx + ny);
                }
            }
        }
    }
}