백준 3055번 탈출 :: 마이구미

이 글은 백준 알고리즘 문제 3055번 "탈출" 을 풀이한다.

본인은 BFS를 활용하여 문제를 해결하였다.

3055번 - https://www.acmicpc.net/problem/3055

기본 DFS, BFS - http://mygumi.tistory.com/102

 

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다. 

 

결국 문제가 원하는 것은 S -> D 로 가는 최소 시간이다.

문제에서 다음과 같은 2가지만 인지하면 된다.

 

1. 고슴도치와 물은 상하좌우로 이동할 수 있다.
2. 물이 찰 예정인 칸은 고슴도치가 이동할 수 없다.

 

물이 찰 예정인 칸은 고슴도치가 이동할 수 없다는 의미는 단순히 물부터 인접한 칸을 채운 후, 고슴도치를 채우면 된다.

물에 대해 BFS를 통해 한번 채우고, 그 다음 고슴도치에 대해 BFS를 통해 채우면 문제를 해결할 수 있다.

돌은 신경쓰지 않으면 아무 지장이 없기 때문에, 고려하지 않는다.

 

기본적인 BFS에 대한 이해를 하고 있다면, 쉽게 소스를 통해 풀이를 이해할 수 있을 것이다.

긴 코드를 볼 수 있지만, 이해를 돕기 위한 것이다.

이해한 후 스스로 줄여보길 바란다.

 

그래프 알고리즘 문제 풀이 - 그래프 문제 카테고리

Github - https://github.com/hotehrud/acmicpc/blob/master/algorithm/graph/3055.java

 

static char[][] map;
static int r, c;
static int[] dx = { -1, 0, 1, 0 };
static int[] dy = { 0, -1, 0, 1 };
static Queue<Point> water = new LinkedList<>();
static Queue<Point> hedgehog = new LinkedList<>();
 
private void solve() {
    // http://mygumi.tistory.com/232
    r = sc.nextInt();
    c = sc.nextInt();
    map = new char[r][c];
 
    for (int i = 0; i < r; i++) {
        char[] input = sc.next().toCharArray();
        for (int j = 0; j < c; j++) {
            map[i][j] = input[j];
 
            if (input[j] == '*') {
                water.add(new Point(i, j));
            }
 
            if (input[j] == 'S') {
                hedgehog.add(new Point(i, j));
            }
        }
    }
 
    int ans = 0;
    while (true) {
        ++ans;
        if (hedgehog.size() == 0) {
            System.out.println("KAKTUS");
            return;
        }
 
        extendWater();
        if (extendHedgehog()) {
            System.out.println(ans);
            return;
        }
    }
}
 
public static void extendWater() {
    int size = water.size();
 
    for (int i = 0; i < size; i++) {
        Point p = water.poll();
 
        for (int j = 0; j < 4; j++) {
            int nx = dx[j] + p.x;
            int ny = dy[j] + p.y;
 
            if (0 <= nx && nx < c && 0 <= ny && ny < r) {
                if (map[ny][nx] == '.') {
                    map[ny][nx] = '*';
                    water.add(new Point(ny, nx));
                }
            }
        }
    }
}
 
public static boolean extendHedgehog() {
    int size = hedgehog.size();
 
    for (int i = 0; i < size; i++) {
        Point p = hedgehog.poll();
 
        for (int j = 0; j < 4; j++) {
            int nx = dx[j] + p.x;
            int ny = dy[j] + p.y;
 
            if (0 <= nx && nx < c && 0 <= ny && ny < r) {
                if (map[ny][nx] == 'D') {
                    hedgehog.add(new Point(ny, nx));
                    return true;
                }
                if (map[ny][nx] == '.') {
                    map[ny][nx] = 'S';
                    hedgehog.add(new Point(ny, nx));
                }
            }
        }
    }
    return false;
}
 
static class Point {
    int x;
    int y;
 
    Point(int y, int x) {
        this.x = x;
        this.y = y;
    }
}