Java - [프로그래머스]159993 - 미로 탈출

출처

https://school.programmers.co.kr/learn/courses/30/lessons/159993?language=java

문제

길을 따라 레버를 열고 출구를 통해 나가는 시간을 측정하여 return하는 문제입니다.

풀이

맵 안에서 최단경로를 찾을 경우 BFS를 먼저 떠올려 접근하였습니다. 현재 제공되는 맵은 String형식이기 때문에 다루기 편한 int배열로 선언을 해준 후 길을 표시하고, 시작/끝/레버 의 위치를 담을 배열을 만들었습니다.

방문 여부를 판단할 visited배열을 선언한 후 bfs를 시작하였습니다. 걸리는 시간은 Start->레버 + 레버->end의 거리를 통해 구할 수 있습니다.

Queue에 int[]객체를 담아 각각 x, y, 현재까지의 거리 세가지를 넣어 순차적으로 탐색을 진행하였고, dx dy 테크닉을 사용하여 이동을 구현하였습니다.

코드

import java.util.*;
class Solution {
    int[][] map;
    int[] dx = new int[] {1, 0, -1, 0};
    int[] dy = new int[] {0, 1, 0, -1};
    boolean[][] visited;

    public boolean isRange(int x, int y) {
        return x >= 0 && x < map.length && y >= 0 && y < map[0].length && map[x][y] > 0 && !visited[x][y];
    }
    
    public int bfs(int[] start, int[] dest) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(start);
        visited[start[0]][start[1]] = true;
        while(!queue.isEmpty()) {
            int[] tmp = queue.poll();
            if(tmp[0] == dest[0] && tmp[1] == dest[1]) {
                return tmp[2];
            }
            for(int i = 0; i < 4; i++) {
                int nx = tmp[0] + dx[i];
                int ny = tmp[1] + dy[i];
                if(isRange(nx, ny)) {
                    visited[nx][ny] = true;
                    queue.add(new int[] {nx, ny, tmp[2] + 1});
                }
            }
        }
        return -1;
    }
    
    public int solution(String[] maps) {
        map = new int[maps.length][maps[0].length()];
        int answer = -1;
        visited = new boolean[maps.length][maps[0].length()];
        int[] start = new int[3];
        int[] lv = new int[3];
        int[] end = new int[3];
        for(int i = 0; i < maps.length; i++) {
            for(int j = 0; j <maps[i].length(); j++) {
                if(maps[i].charAt(j) == 'O') map[i][j] = 1;
                else if (maps[i].charAt(j) == 'L') {
                    lv[0] = i;
                    lv[1] = j;
                    map[i][j] = 1;
                } else if(maps[i].charAt(j) == 'S'){
                    start[0] = i;
                    start[1] = j;
                    map[i][j] = 1;
                } else if(maps[i].charAt(j) == 'E'){
                    map[i][j] = 1;
                    end[0] = i;
                    end[1] = j;
                }
            }
        }
        answer = bfs(start, lv);
        if(answer > -1) {
            visited = new boolean[maps.length][maps[0].length()];
            int tmp = bfs(lv, end);
            if(tmp == -1) {
                answer = -1;
            } else {
                answer += tmp;
            }
        }
        
        
        return answer;
    }
}