[알고리즘] 백준 > #6593. 상범 빌딩

문제링크

백준 #6593. 상범 빌딩

풀이방법

탈출까지 걸리는 최소시간을 묻기 때문에 너비우선탐색을 이용했습니다! 지금까지 다룬 다른 문제들과 달리 level이 추가되었는데요, 이차원으로 풀던 문제를 삼차원으로 바꾸면 됩니다! 기존엔 dy, dx만 가지고 풀 수 있었지만, 이 문제에서는 dl이라는 변수도 추가해 여섯 방향에 대해 탐색을 진행했습니다.

코드

class Solution {
    final int[] dl = {0, 0, 0, 0, +1, -1};
    final int[] dy = {+1, -1, 0, 0, 0, 0};
    final int[] dx = {0, 0, +1, -1, 0, 0};

    final int NOT_VISITED = 0;
    final char DEST = 'E';
    final char GOLD = '#';

    int level;
    int row;
    int col;

    Room startRoom;

    char[][][] building;

    public Solution(int level, int row, int col, Room startRoom, char[][][] building) {
        this.level = level;
        this.row = row;
        this.col = col;
        this.startRoom = startRoom;
        this.building = building;
    }

    public int getMinTimeToEscape() {
        int[][][] visited = new int[level][row][col];

        Queue<Room> q = new LinkedList<>();
        q.offer(startRoom);
        int result = -1;

        while (!q.isEmpty() && (result == -1)) {
            Room head = q.poll();

            for (int i = 0; i < 6; i++) {
                Room nextRoom = new Room(head.level + dl[i], head.y + dy[i], head.x + dx[i]);
                if (isInRange(nextRoom.level, nextRoom.y, nextRoom.x)
                        && building[nextRoom.level][nextRoom.y][nextRoom.x] != GOLD
                        && visited[nextRoom.level][nextRoom.y][nextRoom.x] == NOT_VISITED) {
                    visited[nextRoom.level][nextRoom.y][nextRoom.x] = visited[head.level][head.y][head.x] + 1;
                    q.offer(nextRoom);

                    if (building[nextRoom.level][nextRoom.y][nextRoom.x] == DEST) {
                        result = visited[nextRoom.level][nextRoom.y][nextRoom.x];
                        break;
                    }
                }
            }
        }

        return result;
    }

    private boolean isInRange(int l, int y, int x) {
        return ((l >= 0) && (l < level) && (y >= 0) && (y < row) && (x >= 0) && (x < col));
    }
}

class Room {
    int level;
    int y;
    int x;

    public Room(int level, int y, int x) {
        this.level = level;
        this.y = y;
        this.x = x;
    }

    public Room() { }
}