159993. 미로탈출

문제

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

제한사항

풀이

import java.util.*;

class Solution {
    public int solution(String[] maps) {
        
        
        int answer = 0;
        int n = maps.length;
        int m = maps[0].length();
        char[][] mapArr = new char[n][m];
        int[] start = new int[2];
        int[] end = new int[2];
        int[] lever = new int[2]; 
        
        for(int i = 0; i< n;i++)
            for(int j =0 ;j<m;j++) {
                mapArr[i][j] = maps[i].charAt(j);
                if(mapArr[i][j] == 'S') 
                    start = new int[]{i, j};
                else if(mapArr[i][j] == 'E')
                    end = new int[]{i,j};
                else if(mapArr[i][j] == 'L')
                    lever = new int[]{i,j};
                
            }
        int startToLever = bfs(mapArr, start, lever, 0);
        int leverToEnd = bfs(mapArr,lever, end, 0);
        if(startToLever == -1 || leverToEnd == -1)  
            return -1;
        
        answer = startToLever + leverToEnd;
        return answer;
    }
    
    
    int bfs(char[][] mapArr, int[] start, int[] end, int t) {
        int n = mapArr.length;
        int m = mapArr[0].length;
        boolean[][] visited = new boolean[n][m];
        int[][] dir = {{-1,0}, {1,0}, {0, -1}, {0, 1}};
        Queue<int[]> q = new LinkedList<>();
        
        q.offer(new int[]{start[0], start[1], t});
        while(!q.isEmpty()) {
            int[] cur = q.poll();
            
            if(cur[0] == end[0] && cur[1] == end[1])
                return cur[2];
            
            
            for(int i = 0; i<4; i++) {
                int nr = cur[0] + dir[i][0];
                int nc = cur[1] + dir[i][1];
                
                
                if(nr>=0 && nr<n && nc>=0 && nc<m && mapArr[nr][nc]!='X' &&
                  !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    q.offer(new int[]{nr, nc, cur[2]+1});
                    
                }
            }
        }
        return -1;
    }
}

회고

미로의 구성 요소를 파악만 하면 BFS 또는 DFS를 활용해 풀 수 있는 문제였다. 나는 BFS를 활용하였다. 미로를 탈출하려면 레버를 반드시 당겨야 하기 때문에 출발 지점에서 반드시 레버 지점을 통과해야 한다. 따라서,

1. 출발 지점 -> 레버 지점
2. 레버 지점 -> 탈출구 지점

이렇게 2 구간으로 나눠서 각각의 최단 거리를 구하고 합하면 정답이다. 2 구간 중 둘 중에 하나라도 막혀서 목적지까지 도달하지 못하는 경우가 있으면 -1 반환해 준다.