프로그래머스 미로 탈출

PRGS_미로 탈출 바로가기

문제 설명

미로를 탈출해야한다

미로에는 시작, 끝, 레버, 벽으로 이루어져있다. 레버를 당겨서 문을 열어야 끝에서 나갈 수 있다.

미로 한 칸을 움직이는데 1초가 걸리므로 최단 시간으로 미로를 빠져나갔을 때의 시간을 구하여라

접근 방식

BFS문제이다

시작지점에서 레버까지와 레버에서 끝 지점까지 총 두번의 BFS를 진행하면 된다.

만약에 두 계산 값이 0이 나온다면 끝 지점까지 갈 수 없다는 뜻이므로 -1 을 리턴한다.

코드

import java.util.*;

class Solution {
    static int row, col;
    static char[][] myMap;
    static int[] dx = {0,1,0,-1};
    static int[] dy = {1,0,-1,0};
    
    public int solution(String[] maps) {
        int answer = -1;
        row = maps.length;
        col = maps[0].length();
        
        myMap = new char[row][col];
        
        Node startNode = null;
        Node leverNode = null;
        
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                myMap[i][j] = maps[i].charAt(j);
                if(myMap[i][j] == 'S') startNode = new Node(i,j,0);
                if(myMap[i][j] == 'L') leverNode = new Node(i,j,0);
            }
        }
        
        int startToLever = bfs(startNode, 'L');
        
        if(startToLever != 0){
            int LeverToEnd = bfs(leverNode, 'E');
            if(LeverToEnd != 0){
                answer = startToLever + LeverToEnd;
            }
        }
        
        return answer;
    }
    
    private int bfs(Node node, char goal){
        boolean[][] visit = new boolean[row][col];
        Queue<Node> myQueue = new LinkedList<>();
        visit[node.x][node.y] = true;
        
        int count = 0;
        
        myQueue.offer(node);
        
        while(!myQueue.isEmpty()){
            Node cur = myQueue.poll();
            
            if(myMap[cur.x][cur.y] == goal) {
                count = cur.time;
                break;
            }
            
            for(int i = 0; i < 4; i++){
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                
                if(nx < 0 || ny < 0 || nx == row || ny == col) continue;
                
                if(myMap[nx][ny] == 'X') continue;
                
                if(visit[nx][ny]) continue;
                
                myQueue.offer(new Node(nx, ny, cur.time + 1));
                visit[nx][ny] = true;
                
            }
        }       
        return count;
    }
    
    static class Node{
        int x;
        int y;
        int time;
        
        public Node(int x, int y, int time){
            this.x = x;
            this.y = y;
            this.time = time;
        }
        
    }
}

Disscussion

간단한 BFS문제였다.