[Java] Lv.2 미로 탈출

문제

문제 설명
1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다.
각 칸은 통로 또는 벽으로 구성되어 있으며, 
벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다.

통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 
레버 또한 통로들 중 한 칸에 있습니다. 

따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후
미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 

이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다.
미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 
최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 
미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 

만약, 탈출할 수 없다면 -1을 return 해주세요.

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

프로그래머스

 

문제 풀이

일반적인 BFS 문제인데, 2번 돌려야한다.

출발점에서 레버의 위치를 찾는 BFS 한 번, 레버의 위치에서 도착점의 위치를 찾는 BFS 한 번

자바 코드

import java.util.*;

class Solution {
    public boolean[][] visited;
    public int[][] minTime;
    // 상 하 좌 우
    public int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
    public boolean isFindLever = false, isFindExit = false;
    public int n = 0, m = 0;
    public int sx, sy, lx, ly, ex, ey;
    
    public class Point {
        int x;
        int y;
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public int solution(String[] maps) {
        // maps 크기
        n = maps.length;
        m = maps[0].length();
        
        // 방문처리 배열과 최소 시간 기록 배열
        visited = new boolean[n][m];
        minTime = new int[n][m];

        // 시작점, 레버, 도착점 위치 기록
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                char c = maps[i].charAt(j);
                if(c == 'E') {
                    ex = i;
                    ey = j;
                }
                else if(c == 'S') {
                    sx = i;
                    sy = j;
                }
                else if(c == 'L') {
                    lx = i;
                    ly = j;
                }
            }
        }

        // 시작점 방문 처리 및 시작점부터 레버까지의 최소 시간 찾기
        visited[sx][sy] = true;
        bfs(sx, sy, "L", maps);

        // 레버를 찾았을 경우
        if(isFindLever) {
            // 레버부터 도착점까지의 최소기간 찾기 시작
            visited = new boolean[n][m];
            visited[lx][ly] = true;
            bfs(lx, ly, "E", maps);
        }
        
        // 레버와 도착점을 모두 찾았을 경우
        if(isFindLever && isFindExit) {
            // 도착점까지의 최소 시간 반환
            return minTime[ex][ey];
        }else {// 하나라도 못 찾았을 경우 -1 반환
            return -1;
        }
    }
    private void bfs(int x, int y, String findPos, String[] maps) {
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x, y));
        
        // 큐 빌때까지 반복
        while(!q.isEmpty()) {
            // 현재 위치
            Point cp = q.poll();
            
            // 레버를 찾았을 경우 
            if(findPos.equals("L") && visited[lx][ly]) {
                isFindLever = true;
                return;
            }
            // 도착점을 찾았을 경우
            if(findPos.equals("E") && visited[ex][ey]) {
                isFindExit = true;
                return;
            }
            
            for(int i = 0; i < 4; i++) {
                int nx = cp.x + dx[i];
                int ny = cp.y + dy[i];

                // 맵의 범위를 벗어났을 경우 생략
                if(nx < 0 || ny < 0 || nx >= n || ny >= m) 
                    continue;
                
                // 다음 칸이 장애물이 아니고 방문한 적이 없으면 해당 칸을 방문처리하고 큐에 저장
                if(!(maps[nx].charAt(ny) == 'X') && !visited[nx][ny]) {
                    minTime[nx][ny] = minTime[cp.x][cp.y] + 1;
                    visited[nx][ny] = true;
                    q.add(new Point(nx,ny));
                }
            }
        }
    }
}