[알고리즘] 백준 > #3055. 탈출

문제링크

백준 #3055. 탈출

풀이방법

너비우선탐색을 이용했다. 비버 굴로 이동할 수 있는 최소 시간을 구해야하기 때문에 깊이우선탐색보다 너비우선탐색을 이용하는게 맞다고 생각했다.

물이 확장(확장된 부분을 큐에 넣름)하는 걸 먼저하고, 고슴도치가 이동할 수 있는 곳(비워진 곳으로만 이동가능)을 큐에 저장했다. 그러다 굴이 있는 곳에 도착하면 그 위치까지 걸린 시간을 출력하고 큐가 비워질때까지 굴에 도착하지 못하면 KAKTUS를 출력한다. 일반적인 BFS 문제여서 딱히 설명할게 없다.

코드

import java.util.*;

public class BOJ3055 {

    static int r, c;
    static char[][] map;

    static final char WATER = '*';
    static final char HEDGEHOG = 'S';
    static final char BURROW = 'D';
    static final char EMPTY = '.';

    static int[] dy = {0, 0, +1, -1};
    static int[] dx = {+1, -1, 0, 0};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        r = sc.nextInt();
        c = sc.nextInt();
        sc.nextLine();

        map = new char[r][c];

        Queue<Position> waterQ = new LinkedList<>();
        Position initDPos = new Position();

        for (int i = 0; i < r; i++) {
            String input = sc.nextLine();
            for (int j = 0; j < c; j++) {
                map[i][j] = input.charAt(j);

                if (map[i][j] == WATER) {
                    waterQ.offer(new Position(i, j));
                } else if (map[i][j] == HEDGEHOG) {
                    initDPos.y = i;
                    initDPos.x = j;

                    map[i][j] = '.';
                }
            }
        }

        int result = getShortestEscapeTime(waterQ, initDPos);
        System.out.print((result == -1) ? "KAKTUS" : result);
    }

    private static int getShortestEscapeTime(Queue<Position> waterQ, Position initDPos) {
        Queue<Position> hedgehogQ = new LinkedList<>();
        hedgehogQ.offer(initDPos);

        int[][] times = new int[r][c];

        while (!hedgehogQ.isEmpty()) {
            int preQueueSize = waterQ.size();
            while (--preQueueSize >= 0) {
                Position head = waterQ.poll();

                for (int i = 0; i < 4; i++) {
                    Position next = new Position(head.y + dy[i], head.x + dx[i]);

                    if (isInRange(next.y, next.x) && map[next.y][next.x] == EMPTY) {
                        map[next.y][next.x] = WATER;
                        waterQ.offer(next);
                    }
                }
            }
            int hedgehogQueueSize = hedgehogQ.size();
            while (--hedgehogQueueSize >= 0) {
                Position head = hedgehogQ.poll();

                for (int i = 0; i < 4; i++) {
                    Position next = new Position(head.y + dy[i], head.x + dx[i]);
                    if (isInRange(next.y, next.x) && times[next.y][next.x] == 0) {
                        if (map[next.y][next.x] == BURROW) {
                            return times[head.y][head.x] + 1;
                        } else if (map[next.y][next.x] == EMPTY) {
                            hedgehogQ.offer(next);
                            times[next.y][next.x] = times[head.y][head.x] + 1;
                        }
                    }
                }
            }
        }

        return -1;
    }

    private static boolean isInRange(int y, int x) {
        return ((y >= 0) && (y < r) && (x >= 0) && (x < c));
    }
}

class Position {
    public int y;
    public int x;

    public Position() {
        this.y = 0;
        this.x = 0;
    }

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