[PRG] 159993 미로 탈출 JAVA

https://school.programmers.co.kr/learn/courses/30/lessons/159993

프로그래머스

 

메모리: 77.3 MB

실행시간: 0.12 ms

 

문제분석

완전탐색 (BFS/DFS)

최소경로를 구해야 하므로 BFS를 활용하자 !!
레버를 당기기 전 / 당긴 후 방문체크를 위해 3차원 boolean 배열을 활용하자 !!

걸린 시간

1시간 ⏱️

 

풀이 방법

1. 2차원 맵 생성
2. 시작 지점 찾기
3. BFS
	3 - 1. 인덱스 벗어나거나 X 방문 - continue
	3 - 2. L 방문 - 당기기 전 첫 방문일 경우에만 레버 true로 바꾼 뒤 이동
	3 - 3. S 방문 - (레버 true : answer 저장 후 BFS 종료), (레버 false : 방문체크 후 이동)
	3 - 4. O, S 방문 - 레버 상태의 방문 체크 확인 후 이동


※ 레버 상태 - 0 : false, 1 : true

visited[ ][ ][0] : 레버 false 방문체크
visited[ ][ ][1] : 레버 true 방문체크

 

포인트

문제에서 제시한 대로라면 여러 번 방문할 수 있다.
하지만, 레버 상태에 따라 이미 방문한 곳은 또 갈 필요가 없다.

레버를 당기지 않은 상태에서 레버를 당기기 전에 이미 들린 곳 X
레버를 당긴 상태에서 레버를 당긴 뒤 들린 곳 X

따라서, 3차원 방문체크를 통해 체크해주자 !

 

import java.util.*;

class Solution {
    public int solution(String[] maps) {
        int answer = -1;

        int M = maps[0].length();
        int N = maps.length;

        // 미로 맵 생성
        char[][] map = new char[N][M];

        // 출발지점
        int startX = 0;
        int startY = 0;

        // 1차원 maps를 2차원 맵에 옮기기
        for(int i = 0; i < maps.length; i ++) {
            for(int j = 0; j < maps[0].length(); j ++) {
                map[i][j] = maps[i].charAt(j);
                if(map[i][j] == 'S') {
                    startX = i;
                    startY = j;
                }
            }
        }

        // 4방탐색
        int[] dx = {0, -1, 0, 1};
        int[] dy = {-1, 0, 1, 0};

        // bfs
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[] {startX, startY, 0, 0}); // x좌표, y좌표, 레버 여부, time
        boolean[][][] visited = new boolean[N][M][2]; // 방문체크 2type (레버 당기기 전, 레버 당긴 후)
        visited[startX][startY][0] = true; // 시작지점 방문체크

        outer : while(!q.isEmpty()) {
            int time = q.size(); // 1 depth
            for(int t = 0; t < time; t ++) {
                int[] temp = q.poll();
                for(int d = 0; d < 4; d ++) { // 4방 탐색
                    int nx = temp[0] + dx[d];
                    int ny = temp[1] + dy[d];

                    // 맵을 벗어나거나 벽인 경우
                    if(nx < 0 || nx >= N || ny < 0 || ny >= M || map[nx][ny] == 'X') continue; 

                    // 레버인 경우
                    if(map[nx][ny] == 'L' && !visited[nx][ny][1] && temp[2] == 0) {
                        // 당기기 전 첫 방문
                        q.offer(new int[] {nx, ny, 1, temp[3] + 1});
                        visited[nx][ny][1] = true;
                    }

                    // 출구인 경우
                    else if(map[nx][ny] == 'E') {
                        // 레버 당기기 전
                        if(temp[2] == 0 && !visited[nx][ny][0]) {
                            q.offer(new int[] {nx, ny, temp[2], temp[3] + 1});
                            visited[nx][ny][0] = true;
                        }
                        // 레버 당긴 후
                        if(temp[2] == 1) {
                            answer = temp[3] + 1;
                            break outer;
                        }
                    }

                    // 시작 지점 || 통로
                    else if(map[nx][ny] == 'S' || map[nx][ny] == 'O') {
                        if(!visited[nx][ny][temp[2]]) { // 첫 방문
                            q.offer(new int[] {nx, ny, temp[2], temp[3] + 1});
                            visited[nx][ny][temp[2]] = true;
                        }
                    }
                }
            }
        }

        return answer;
    }
}