[JAVA] 프로그래머스 LEVEL2 미로 탈출

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

프로그래머스

코딩테스트 연습 > 연습문제 > 미로 탈출

 

난이도: LEVEL2

알고리즘 유형: BFS

풀이 설명  

시작 → 레버 

레버 → 출구 

각 거리를 BFS를 통해서 최단 거리를 찾는다. 

시작에서 레버까지 이동 OR 레버에서 출구까지 도달하지 못하면 -1 반환한다.

 

각 메소드 설명

 

1. init

1차원 String 배열 maps를 2차원 int 배열 map 변환

시작 좌표, 레버 좌표, 출구 좌표를 static int로 기록  

 

2. validation

indexoutofboundsexception 예외 방지를 위한 좌표 범위 검사 

 

3. move

BFS를 하는 핵심 로직 시작 → 레버 /  레버 → 출구 2개의 BFS를 1개의 메소드에서 진행한다. 

매개변수로 시작 좌표와 도착 좌표를 받게 해서 1개의 메소드로 진행 가능하게 했다.

내부에서 다음 좌표에 대한 좌표 범위 검사를 validation에게 위임한다. 

 

4. solution

프로그래머스에서 실행하는 메소드

내가 정의한 init을 먼저 실행하고 

move 메소드를 실행한다.

중간 중간 move 반환값이 INF면 -1을 바로 반환한다. (해당 좌표로 이동 불가능의 의미)

정답 코드 

import java.util.*;
class Solution {
    static final int INF = Integer.MAX_VALUE;
    static int [][] map;
    // 시작, 레버, 출구 좌표 
    static int sx, sy, lx, ly, ex, ey;
    // maps 크기 
    static int n,m;
    // 좌표이동을 위한 배열 
    static int [] arx = {-1,1,0,0};
    static int [] ary = {0,0,-1,1};
    public int solution(String[] maps) {
        init(maps);
        
        int answer = 0; 
        // 시작 -> 레버
        int moveLever = move(sx, sy, lx, ly);
        if(moveLever == INF) return -1;
        answer += moveLever;
        
        // 레버 -> 출구 
        int moveEnd = move(lx, ly, ex, ey);
        if(moveEnd == INF) return -1;
        answer +=  moveEnd;
        
        return answer;
    }
    private static int move(int start_x, int start_y, int end_x, int end_y){
        Queue<int[]> q = new LinkedList<>();
        int [][] memo = new int [n][m];
        for(int i = 0; i < n; i++){
            Arrays.fill(memo[i], INF);
        }
        memo[start_x][start_y] = 0;
        q.add(new int [] {start_x, start_y});
        while(!q.isEmpty()){
            int [] cur = q.poll();
            for(int i = 0; i < 4; i++){
                int nx = arx[i] + cur[0];
                int ny = ary[i] + cur[1];
                if(!validation(nx, ny) || map[nx][ny] == INF) continue;
                if(memo[cur[0]][cur[1]] + 1 < memo[nx][ny]){
                    memo[nx][ny] = memo[cur[0]][cur[1]] + 1;
                    q.add(new int [] {nx, ny});
                }
            }
        }
        return memo[end_x][end_y];
    }
    // 범위 검사기 
    private static boolean validation(int nx, int ny){
        if(0 <= nx && 0 <= ny && nx < n && ny < m) return true;
        return false;
    }
    // 2차원 배열 map 생성 
    private static void init(String[] maps){
        n = maps.length;
        m = maps[0].length();
        map = new int [n][m];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                char cur = maps[i].charAt(j);
                if(cur == 'O') continue;
                if(cur == 'X') map[i][j] = INF;
                else if(cur == 'S'){
                    sx = i;
                    sy = j;
                }
                else if(cur == 'L'){
                    lx = i;
                    ly = j;
                }
                else if(cur == 'E'){
                    ex = i;
                    ey = j;
                }
            }
        }
    } 
}