[프로그래머스] 프로그래머스 미로 탈출 java 자바 (level2)

• 미로 탈출

문제 설명

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을 반환합니다.

나의풀이

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

class Solution {
    
    static int xLen, yLen;//가로세로 크기 
    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 = {0,0,-1,1};
    static int[] dy = {-1,1,0,0};

    // 좌표를 담을 클래스
    static public class Node{
        int x, y, cnt;//x좌표, y좌표, 이동한 초 
        public Node(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
    
    public static int bfs1(int x, int y) {//S좌표
        Queue<Node> q = new LinkedList<>();//큐 선언시 linkedlist이용 
        q.offer(new Node(x, y, 0)); //S좌표지점을 q에 삽입 
        visited[x][y] = true;//방문처리

        while(!q.isEmpty()) {//q가 빌때까지 반복 
            Node now = q.poll(); //q에서 뽑아옴 

            // 4방향 상하좌우 
            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 >= xLen || nextY >= yLen) {
                    continue;
                }

                // 벽이거나 방문한 곳이면 
                if(map[nextX][nextY] == 'X' || visited[nextX][nextY] == true) {
                    continue;
                }

                //레버에 도착했으면 1초 증가해서 반환 
                if(map[nextX][nextY] == 'L') {
                    return now.cnt+1;
                }

                q.offer(new Node(nextX, nextY, now.cnt + 1));//갈수 있는 지점인데 레버는 아닐때 1초 증가해서 큐에 넣어주기 
                visited[nextX][nextY] = true;//방문처리 
            }

        }
        return -1;//레버에 도달하지 못하면 -1반환 
    }

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

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

            // 4방향 상하좌우 
            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 >= xLen || nextY >= yLen) {
                    continue;
                }

                // 벽이거나 방문한 곳이면 
                if(map[nextX][nextY] == 'X' || visited[nextX][nextY] == true) {
                    continue;
                }

                //종료에 도착했으면 1초 증가해서 반환 
                if(map[nextX][nextY] == 'E') {
                    return now.cnt+1;
                }

                q.offer(new Node(nextX, nextY, now.cnt + 1));//갈수 있는 지점인데 종료료는 아닐때 1초 증가해서 큐에 넣어주기
                visited[nextX][nextY] = true;//방문처리 
            }

        }
        return -1;//종료에 도달하지 못하면 -1반환 
    }
    
    public int solution(String[] maps) {
        int answer = 0;
        int toLever = 0;
        int toEnd = 0;
           
        map = new char[maps.length][];
        
        xLen = maps.length;
        yLen = maps[0].length();
        
        for(int i = 0; i < xLen; i++) {
        	for(int j = 0; j < yLen; j++){
        		map[i]= maps[i].toCharArray();
        		
        		if(map[i][j] == 'S') { // 시작
        			S[0] = i; S[1] = j;
        		} else if(map[i][j] == 'L') { // 레버
        			L[0] = i; L[1] = j;
        		} else if(map[i][j] == 'E') { // 종료
        			E[0] = i; E[1] = j;
        		}  
        	}
        }
        
        // 레버까지의 최소거리 
        visited = new boolean[xLen][yLen];
        toLever = bfs1(S[0], S[1]);
        
        // 레버에서 종료까지의 최소거리
        visited = new boolean[xLen][yLen];//방문기록을 초기화 
        toEnd = bfs2(L[0], L[1]);
        
        //시작-> 레버 or 레버->종료 중 하나라도 도달하지 못하면 
        if(toLever == -1 || toEnd == -1) {
        	return -1;
        } 
        return toLever + toEnd;
        
    }
}

Tip.

큐 선언시에는 linkedlist를 사용한다.

bfs를 두번쓰면 해결되는 문제. bfs 풀이를 위해 큐를 사용해서 이동가능한 방향별로 각 좌표를 큐에 넣어주고 큐의 첫번째 째 값을 빼면서 큐가 빌때까지 다시 탐색을 반복하는 식이다.