(java)프로그래머스 미로 탈출

프로그래머스

문제 풀이

문제를 보자 마자 bfs라는 풀이법을 떠올렸다. 먼저 레버에 도착하는 최소의 거리를 구하고 또 레버에서 bfs를 시작해서 출구로 가는 최소한의 거리를 구하면 된다. 그런데 레버에 도착하지 못하는 경우에는 바로 return -1을 해주어야 하는데 이 경우를 찾지 못해서 조금 해맸다.

import java.util.*;

class Solution {
    public int solution(String[] maps) {        
        int N = maps.length;
        int M = maps[0].length();
        char[][] map = new char[N][M];
        for(int i = 0; i < N; i++){
            map[i] = maps[i].toCharArray();
        }
        
        int[] first = new int[3];
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(map[i][j] == 'S'){
                    first = new int[]{i, j, 0}; // 좌표, 깊이
                }            
            }
        }
        int startX = first[0];
        int startY = first[1];
        
        boolean isMetL = false; // 레버를 만났나
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(first);
        int[] dx = new int[]{1, -1, 0, 0};
        int[] dy = new int[]{0, 0, 1, -1};
        boolean[][] visited = new boolean[N][M];
        visited[first[0]][first[1]] = true;
        while(!queue.isEmpty()){
            int[] now = queue.poll();
            boolean found = false;
            for(int i = 0; i < 4; i++){
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                if(nx < 0 || nx >= N || ny < 0 || ny >= M || map[nx][ny] == 'X' || visited[nx][ny]) continue;
                if(map[nx][ny] == 'L') {
                    first = new int[]{nx, ny, now[2] + 1};
                    found = true;
                    break;
                }
                queue.offer(new int[]{nx, ny, now[2] + 1});
                visited[nx][ny] = true;
            }
            if(found) break;
        }
        if(first[0] == startX && first[1] == startY) return -1;
        queue = new ArrayDeque<>();
        queue.offer(first);
        visited = new boolean[N][M];
        while(!queue.isEmpty()){
            int[] now = queue.poll();
            for(int i = 0; i < 4; i++){
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                if(nx < 0 || nx >= N || ny < 0 || ny >= M || map[nx][ny] == 'X' || visited[nx][ny]) continue;
                if(map[nx][ny] == 'E') {
                    return now[2] + 1;
                }
                queue.offer(new int[]{nx, ny, now[2] + 1});
                visited[nx][ny] = true;
            }
        }
        return -1;
    }
}