프로그래머스 Lv.2 미로 탈출

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

문제 설명

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 알고리즘을 사용하여 각 최단 거리를 구해 총거리를 구해줍니다.

풀이

import java.util.*;

class Solution {
    public int solution(String[] maps) {
        int answer = -1;
        
        int n = maps.length;
        int m = maps[0].length();
        
        // 시작 지점 
        int[] start = new int[2];
        // 레버 
        int[] lever = new int[2];
        // 출구 
        int[] end = new int[2];
        
        // 시작 지점, 레버, 츨구 좌표 저장 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                char ch = maps[i].charAt(j);
                
                if (ch == 'S') {   
                    start[0] = i;
                    start[1] = j;
                } else if (ch == 'L') { 
                    lever[0] = i;
                    lever[1] = j;
                } else if (ch == 'E') { 
                    end[0] = i;
                    end[1] = j;
                }
            }
        }
        
        int a = bfs(maps, start, lever);
        int b = bfs(maps, lever, end);

        if (a != -1 && b != -1) {
            answer = a + b;
        } 
        
        return answer;
    }
    
    public int bfs(String[] maps, int[] start, int[] end) {     
        int n = maps.length;
        int m = maps[0].length();
        
        // 상, 하, 좌, 우 
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
                
        Queue<int[]> q = new LinkedList<>(); 
		int[][] visited = new int[n][m];   

        int x = start[0];
        int y = start[1];
        
        q.add(new int[]{x, y});

        while(!q.isEmpty()) {
            int[] now = q.poll();
            x = now[0];
            y = now[1];
            
            if (x == end[0] && y == end[1]) {
                return visited[x][y];
            }
            
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                // 미로의 범위 밖, 벽, 이미 방문한 경우 생략  
                if (nx < 0 || nx >= n || ny < 0 || ny >= m || maps[nx].charAt(ny) == 'X' || visited[nx][ny] > 0) {
                    continue;
                }
                
                // 이동 거리 +1
                visited[nx][ny] = visited[x][y] + 1;    
                q.add(new int[]{nx, ny});
            }
        }
        return -1;
    } 
}

결과