Programmers 159993 - 미로 탈출

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

프로그래머스

 

출발지 → 레버 → 출구 순으로 방문을 해야만 탈출할 수 있다.

미로 1칸을 이동하는 것을 1초라고 가정했을 때 최대한 빠르게 미로를 빠져나가는 데 걸리는 시간을 구하는 것이다.

즉 최단거리를 구해야 하고 BFS를 사용하면 될 것 같다.

탈출하지 못한 경우 -1을 반환하면 된다.

우선 주어진 배열은 String [ ] maps이다. 문자열로 “SOOOL” 이런 식으로 값이 들어가 있다.

S는 출발지, E 출구, L 레버, O 통로, X 벽이다.

문자열이라는 것은 결국 char []을 다루는 것과 동일하다.

또한 시간을 저장하기 위한 별도의 배열이 필요하다 이 배열은 시작 위치에서부터 탐색이 될수록 1씩 증가시켜 가며 값을 저장할 것이다.

출발지 → 레버로 도달하지 못하면 -1을 반환한다.

그 후 레버 → 출구 과정에서 도달하지 못하면 마찬가지로 -1을 반환한다.

최종 풀이는 다음과 같다.

1. S에서 L까지 BFS를 통해 걸리는 최소 시간을 구한다.
2. L에서 O를 목표로 BFS를 통해 걸리는 최소 시간을 구한다.
3. 두 최소 시간을 통해 정답을 반환한다.

import java.util.*;

class Solution {
    
    static class Point {
        int r;
        int c;
        
        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
        
        // 편의상 간단하게 구현
        @Override
        public boolean equals(Object o) {
            Point other = (Point) o;
            return r == other.r && c == other.c;
        }
    }
    static final int[] DR = {-1, 1, 0, 0};
    static final int[] DC = {0, 0, -1, 1};
    static Point start;
    static Point lever;
    static Point goal;
    
    public int solution(String[] maps) {
        int startToLever = 0;
        int leverToGoal = 0;
        
        for (int row = 0; row < maps.length; row++) {
            for (int col = 0; col < maps[row].length(); col++) {
                switch (maps[row].charAt(col)) {
                    case 'S' -> start = new Point(row, col);
                    case 'L' -> lever = new Point(row, col);
                    case 'E' -> goal = new Point(row, col);
                }
            }
        }
        
        startToLever = bfs(start, lever, maps);
        leverToGoal = bfs(lever, goal, maps);
        
        // 도달하지 못하는 경우
        if (startToLever == 0 || leverToGoal == 0) return -1;
        
        return startToLever + leverToGoal;
    }
    
    private int bfs(Point start, Point goal, String[] maps) {
        
        int[][] times = new int[maps.length][maps[0].length()];
        Queue<Point> q = new LinkedList<>();
        q.add(start);
        
        while (!q.isEmpty()) {
            Point curr = q.poll();
            
            if (curr.equals(goal)) {
                return times[curr.r][curr.c];
            }
            
            for (int d = 0; d < 4; d++) {
                int nr = curr.r + DR[d];
                int nc = curr.c + DC[d];
                
                if (nr < 0 || nr >= maps.length || nc < 0 || nc >= maps[nr].length()) continue;
                if (maps[nr].charAt(nc) == 'X') continue;
                if (times[nr][nc] != 0) continue;
                
                times[nr][nc] = times[curr.r][curr.c] + 1;
                q.add(new Point(nr, nc));
            }
        }
        
        return 0; // goal에 도달하지 못한 경우
    }
}

 

방문 판단을 times 배열의 값으로 하고 있는데 시작점을 별도로 방문처리 하지 않았다. 

이는 어차피 방문 지점을 BFS로 재방문한다 해도 답에 영향이 없기 때문에 최종 답 처리 편의를 위해 방문처리를 생략했다.