프로그래머스, 미로 탈출(java)

문제 설명

S에서 시작해서 E로 탈출하는 최단 시간을 구하는 문제이다. 단, 'X'로 표시된 벽은 지나갈 수 없고 'L'로 표시된 레버를 먼저 올려야만 E로 갈 수 있다. 즉, 우리는 L을 먼저 들렸다가 E로 도착해야 하는 것이다.

 

문제에서는 이동 방향이 주어지지 않았기 때문에 나는 임의로 상하좌우를 탐색했다.

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

프로그래머스

문제 풀이

첫 번째 접근

최단 거리라 너비 우선 탐색으로 푸는 게 제일 좋다고 판단했다.

그러므로 일단 시작 위치와 끝, 그리고 레버에 있는 위치를 찾아준다. 다음에는 시작에서 레버까지의 최단  시간을 구한다. 만일 레버의 시간을 확인했는데, 최단 시간이 갱신되지 않았으면 이는 레버까지 가지 못한다는 의미이므로 -1을 반환한다. 그리고 레버에서부터 끝까지 가는 데 걸리는 최단 시간을 구한다. 이때도 종료 위치의 시간을 확인해 최단 시간으로 갱신되지 않으면 -1을 반환한다. 레버와 종료 위치까지 갈 수 있다면 두 개의 시간을 더해주면 된다.

코드

java

import java.util.*;

class Pair{
    int row;
    int col;
    
    Pair(int row, int col){
        this.row = row;
        this.col = col;
    }
}

class Solution {
    public static int[] dR = {-1, 0, 1, 0}; //북동남서
    public static int[] dC = {0, 1, 0, -1};
    public static int[][] count;
    public static int rowLength, colLength;
    
    public int solution(String[] maps) {
        int answer = 0;
        rowLength = maps.length;
        colLength = maps[0].length();
        Pair arr[] = new Pair[3];
        
        for(int i=0; i<rowLength; i++){
            String tmp = maps[i];
            for(int j=0; j<colLength; j++){
                if(tmp.charAt(j) == 'S'){
                    arr[0] = new Pair(i, j);
                }
                if(tmp.charAt(j) == 'E'){
                    arr[1] = new Pair(i, j);
                }
                if(tmp.charAt(j) == 'L'){
                    arr[2] = new Pair(i, j);
                }
            }
        }
        
        int goToLever = bfs(arr[0], arr[2], 'L', maps);
        
        if(goToLever == 1001){
            return -1;
        }
        
        int goToExit = bfs(arr[2], arr[1], 'E', maps);
        if(goToExit == 1001){
            return -1;
        }
        answer = goToLever + goToExit;
        //System.out.println(answer);
        return answer;
    }
    
        
    public int bfs(Pair start, Pair end, char target, String[] map){
        Queue<Pair> queue = new LinkedList<>();
        queue.add(start);
        count = new int[rowLength][colLength];
        //System.out.println(end.row + " " + end.col);
        for(int i=0; i<rowLength; i++){
            for(int j=0; j<colLength; j++){
                count[i][j] = 1001;
            }
        }
        //System.out.println(rowLength + " " + colLength);
        count[start.row][start.col] = 0;
        
        while(!queue.isEmpty()){
            Pair current = queue.poll();
            int cR = current.row;
            int cC = current.col;
            int cCount = count[cR][cC];
            
            if(cR == end.row && cC == end.col){
                break;
            }
            
            for(int i=0; i<4; i++){
                int nR = cR + dR[i];
                int nC = cC + dC[i];
                //int nCount = count[nR][nC];
                
                if(nR >= 0 && nR < rowLength && nC >= 0 && nC < colLength){
                    if(map[nR].charAt(nC) != 'X' && count[nR][nC] > cCount+1){
                        count[nR][nC] = cCount+1;
                        queue.add(new Pair(nR, nC));
                    }
                }
            }
        }
        
        return count[end.row][end.col];
    }

}