미로 탈출

오랜만에 풀어보는 프로그래머스다. BFS류의 문제였는데 분명히 풀어본 유형이라고 생각하고 접근했는데 내가 생각했던 방법과 잘 맞아서 잘 풀었던거 같다. Java에는 Struct가 존재하지 않기에 클래스를 사용해주었다. 여러가지 경험에서 느낀결과 BFS류의 문제를 풀때는 클래스를 만들어서 풀어주는게 훨씬 가독성이 좋았다.

이 문제의 핵심은 레버를 돌리고 탈출을 해야한다. 그리고 모든 출구 및 통로는 레버를 돌리지 않은 상태에서도 여러번 지나갈 수 있다가 핵심인데, 그냥 무심코 일반적인 BFS접근으로 visited 배열을 만들었다가는 망한다. 3차원 배열로 레버를 돌렸을때 혹은 돌리지 않았을때로 나누어서 탐색을 돌려야지 통과를 할 수 있는 문제다.

앞으로는 좀 프로그래머스 문제를 위주로 풀어야겠다. 한참 고인물 때는 랭킹 500위권안으로 갔는데 안풀다보니 벌써 천으로 밀렸다...

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

class Route{
    int x,y,dist,lever; 
    Route(int x, int y, int dist, int lever){
        this.x = x; 
        this.y = y; 
        this.dist = dist; 
        this.lever = lever; 
    }
}

class Solution {
    int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}}; 
    public int solution(String[] maps) {
        int answer = 0;
        boolean[][][] visited = new boolean[maps.length][maps[0].length()][2]; 
        Queue<Route> q = new LinkedList<>(); 
        
        for(int i = 0; i < maps.length; i++){
            for(int j = 0; j < maps[i].length(); j++){
                if(maps[i].charAt(j) == 'S'){
                    visited[i][j][0] = true; 
                    //visited[i][j][1] = true; 
                    q.add(new Route(i,j,0,0));
                    break; 
                }
            }
        }
        
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0; i < size; i++){
                Route route = q.poll(); 
                int x = route.x, y = route.y, dist = route.dist; 
                int lever = route.lever; 
                
                if(maps[x].charAt(y) == 'E' && lever == 1) return dist; 
                
                for(int[] d : dir){
                    int nX = x + d[0]; 
                    int nY = y + d[1]; 
                    
                    if(nX < 0 || nY < 0 || nX >= maps.length || nY >= maps[0].length() || maps[nX].charAt(nY) == 'X' || visited[nX][nY][lever]) continue; 
                    
                    if(maps[nX].charAt(nY) == 'L'){
                        visited[nX][nY][1] = true;
                        q.add(new Route(nX,nY,dist+1,1)); 
                    }
                    
                    else{
                        visited[nX][nY][lever] = true; 
                        q.add(new Route(nX,nY,dist+1,lever)); 
                    }
                }
            }
        }
        return -1; 
    }
}