[프로그래머스] [Level2] 미로 탈출 (BFS) (JAVA)

https://school.programmers.co.kr/learn/courses/30/lessons/159993?language=java 

프로그래머스

---

미로 탈출

문제 설명

1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

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

---

제한사항

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

 

입출력 예mapsresult

["SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"]	16
["LOOXS","OOOOX","OOOOO","OOOOO","EOOOO"]	-1

 

---

입출력 예 설명

입출력 예 #1

주어진 문자열은 다음과 같은 미로이며

다음과 같이 이동하면 가장 빠른 시간에 탈출할 수 있습니다.

4번 이동하여 레버를 당기고 출구까지 이동하면 총 16초의 시간이 걸립니다. 따라서 16을 반환합니다.

입출력 예 #2

주어진 문자열은 다음과 같은 미로입니다.

시작 지점에서 이동할 수 있는 공간이 없어서 탈출할 수 없습니다. 따라서 -1을 반환합니다.

---

※ JAVA 코드 (미로 탈출)

import java.io.*;
import java.util.*;

class Solution {
    
    static int N, M;
    static int[] S = new int[2];
    static int[] L = new int[2];
    static int[] E = new int[2];
    static char[][] map;
    static boolean[][] visited;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};

    // 좌표를 담을 클래스
    static public class Node{
        int x, y, cnt;
        public Node(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
    
    public static int toLever(int x, int y) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x, y, 0));
        visited[x][y] = true;

        while(!q.isEmpty()) {
            Node now = q.poll();

            // 좌표 이동 상하좌우
            for(int i = 0; i < 4; i++) {
                int nextX = now.x + dx[i];
                int nextY = now.y + dy[i];

                // 맵의 범위를 벗어나면
                if(nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
                    continue;
                }

                // 벽이라면
                if(map[nextX][nextY] == 'X' || visited[nextX][nextY] == true) {
                    continue;
                }

                if(map[nextX][nextY] == 'L') {
                    return now.cnt+1;
                }

                q.offer(new Node(nextX, nextY, now.cnt + 1));
                visited[nextX][nextY] = true;
            }

        }
        return -1;
    }

    public static int toEnd(int x, int y) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x, y, 0));
        visited[x][y] = true;

        while(!q.isEmpty()) {
            Node now = q.poll();

            // 좌표 이동 상하좌우
            for(int i = 0; i < 4; i++) {
                int nextX = now.x + dx[i];
                int nextY = now.y + dy[i];

                // 맵의 범위를 벗어나면
                if(nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
                    continue;
                }

                // 벽이라면
                if(map[nextX][nextY] == 'X' || visited[nextX][nextY] == true) {
                    continue;
                }

                if(map[nextX][nextY] == 'E') {
                    return now.cnt+1;
                }

                q.offer(new Node(nextX, nextY, now.cnt + 1));
                visited[nextX][nextY] = true;
            }

        }
        return -1;
    }
    
    public int solution(String[] maps) {
        int answer = 0;
        int sToL = 0;
        int lToE = 0;
        int n = maps.length;
        int m = maps[0].length();
        
        // 맵 크기 설정
        map = new char[n][m];
        
        N = n;
        M = m;
        
        for(int i = 0; i < N; i++) {
        	for(int j = 0; j < M; j++){
        		char c = maps[i].charAt(j);
        		// 맵에 담아준다
        		map[i][j] = c;
        		if(c == 'S') { // 시작지점
        			// 시작 (x, y) 좌표
        			S[0] = i; S[1] = j;
        		} else if(c == 'L') { // 레버지점
        			// 레버 (x, y) 좌표
        			L[0] = i; L[1] = j;
        		} else if(c == 'E') { // 종료지점
        			// 종료 (x, y) 좌표
        			E[0] = i; E[1] = j;
        		}  
        	}
        }
        
        // 시작지점 -> 레버
        visited = new boolean[n][m];
        sToL = toLever(S[0], S[1]);
        // 레버 -> 종료지점
        visited = new boolean[n][m];
        lToE = toEnd(L[0], L[1]);
        
        if(sToL == -1 || lToE == -1) {
        	answer = -1;
        } else {
        	answer = sToL + lToE;
        }
        return answer;
    }
}

---

※ 생각정리 (미로 탈출)
1. 시작지점, 레버지점, 종료지점의 좌표를 구한다.
2. 시작지점에서 레버지점까지의 최단거리를 구한다.
3. 레버지점에서 종료지점까지의 최단거리를 구한다.
4. 두 값을 합한다.
5. 탐색중 큐를 탈출한다면(더이상 이동방법이 없다면) -1을 출력한다.
 
-새벽코딩-