Lv.2 미로 탈출 [JAVA]

문제 링크

성공 여부(걸린 시간): 성공(34분 37초)

아이디어

이 문제는 레버를 먼저 작동시켜야 탈출이 가능한 구조이기 때문에 레버를 출발지점으로 생각해서
S를 향해 한번, E를 향해 한번 BFS를 총 두 번 수행하는 방식으로 해결할 수 있다.

1. 레버 위치를 기준점으로 두고 BFS를 두 번 수행한다.
   • 첫 번째 BFS: 레버에서 시작점(S)까지의 거리
   • 두 번째 BFS: 레버에서 도착점(E)까지의 거리
2. 두 거리의 합이 곧 정답이 되며, 이 중 하나라도 도달하지 못하면(-1 반환) 탈출이 불가능한 경우이므로 -1을 반환한다.

핵심 구현 포인트

• BFS를 위한 visited 배열 초기화
• 레버 위치부터 S, E까지 각각 도달 가능 여부 및 거리 계산
• 도달하지 못한 경우 -1 반환

정답 코드

import java.util.*;

class Solution {
    static int N, M;
    static int [][] map;
    static int [] button;

    public int solution(String[] maps) {
        N = maps.length;
        M = maps[0].length();

        int [] startPoint = {0, 0};
        int [] endPoint = {0, 0};
        button = new int[]{0, 0}; // 레버 위치
        map = new int[N][M];

        // 맵 기호 처리: S=0, E=1, O=2, X=3, L=-1
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                char x = maps[i].charAt(j);
                if(x == 'S'){
                    map[i][j] = 0;
                    startPoint = new int[]{i, j};
                } else if(x == 'E'){
                    map[i][j] = 1;
                    endPoint = new int[]{i, j};
                } else if(x == 'O'){
                    map[i][j] = 2;
                } else if(x == 'X'){
                    map[i][j] = 3;
                } else if(x == 'L'){
                    map[i][j] = -1;
                    button = new int[]{i, j};
                }
            }
        }

        int getToS = BFS(startPoint);
        int getToE = BFS(endPoint);

        if(getToS != -1 && getToE != -1){
            return getToS + getToE;
        }
        return -1;
    }

    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    static int BFS(int[] target){
        int[][] visited = new int[N][M];
        for(int i = 0; i < N; i++){
            Arrays.fill(visited[i], -1);
        }

        ArrayDeque<int[]> q = new ArrayDeque<>();
        q.add(new int[]{button[0], button[1]});
        visited[button[0]][button[1]] = 0;

        while(!q.isEmpty()){
            int[] cur = q.poll();
            int x = cur[0], y = cur[1];

            if(x == target[0] && y == target[1]){
                return visited[x][y];
            }

            for(int i = 0; i < 4; i++){
                int mx = x + dx[i];
                int my = y + dy[i];
                if(canGo(mx, my) && visited[mx][my] == -1 && map[mx][my] != 3){
                    q.add(new int[]{mx, my});
                    visited[mx][my] = visited[x][y] + 1;
                }
            }
        }

        return -1;
    }

    static boolean canGo(int x, int y){
        return x >= 0 && y >= 0 && x < N && y < M;
    }
}