프로그래머스 - 미로 탈출

문제

풀이

• 레버까지의 bfs를 구하고 레버에서부터 도착점까지의 bfs를 구해서 더한다

유의할 점

코드

import java.util.*; 
class Solution {
    public int solution(String[] maps) {
        int answer = 0;
        int[]dx ={-1,0,1,0}; 
        int[]dy = {0,1,0,-1}; 
        Queue<Node> q = new LinkedList<>(); 
        int[][] dist = new int[maps.length][maps[0].length()]; 
        for(int i=0; i<dist.length; i++) Arrays.fill(dist[i],-1); 
        
        Node exit = null;
        Node lever = null;
        
        //레버를 두번 당기면 되지 않을까?
        for(int i=0; i<maps.length; i++){
            for(int j=0 ;j<maps[i].length(); j++){
                if (maps[i].charAt(j)=='S') {
                    q.add(new Node(i,j)); 
                    dist[i][j] = 0;   
                } else if (maps[i].charAt(j) =='L') lever = new Node(i,j); 
                else if (maps[i].charAt(j)=='E') exit = new Node(i,j); 
            }
        }
        
        int distToLever=-1; 
        
        while(!q.isEmpty()){
            Node p = q.poll(); 
            
            for(int i=0; i<4; i++){
                int nx = p.x+dx[i]; 
                int ny = p.y+dy[i]; 
                
                if(nx<0||ny<0||nx>=maps.length||ny>=maps[0].length()) continue; 
                if(dist[nx][ny]>-1 || maps[nx].charAt(ny)=='X') continue; 
                dist[nx][ny] = dist[p.x][p.y]+1;
                if(nx == lever.x && ny == lever.y) {
                    distToLever = dist[nx][ny]; 
                    q.clear(); 
                    break; 
                }
                q.add(new Node(nx,ny)); 
            }
        }
        for(int i=0; i<dist.length; i++) Arrays.fill(dist[i],-1); 
            dist[lever.x][lever.y] = 0 ;
            q.add(lever); 
            
            int distToExit = -1; 
            while(!q.isEmpty()){
                  Node p = q.poll(); 
            
            for(int i=0; i<4; i++){
                int nx = p.x+dx[i]; 
                int ny = p.y+dy[i]; 
                
                if(nx<0||ny<0||nx>=maps.length||ny>=maps[0].length()) continue; 
                if(dist[nx][ny]>-1 || maps[nx].charAt(ny)=='X') continue; 
                dist[nx][ny] = dist[p.x][p.y]+1;
                if(nx == exit.x && ny == exit.y) {
                    distToExit = dist[nx][ny]; 
                    q.clear(); 
                    break; 
                }
                q.add(new Node(nx,ny)); 
            }
        }
        if(distToLever==-1 || distToExit== -1) return -1; 
        
        return distToLever+distToExit;
    }
    
    class Node{
        int x, y; 
        Node (int x, int y){
            this.x = x; 
            this.y = y; 
        }
    }
}