백준) 3055 탈출

탈출

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

물이 인접한 칸으로 계속 불어날 때, 고슴도치가 물에 닿지 않고 목표지점까지 갈 수 있는지,

간다면 최단거리는 몇인지 알아내야 한다.

그래프 탐색문제이며, 최단거리를 알아내야 하므로 BFS를 써보기로 했다.

물과 고슴도치를 모두 큐에 넣고 BFS를 돌려버릴 수 있겠다.

하지만 둘 다 같은 시간에 같은 칸에 도착한다면 물이 이기는 경우를 처리할 수 없다.(내 생각에는)

그래서 물은 고슴도치의 이동에 전혀 영향을 받지 않으므로,

물만 BFS를 먼저 돌려서 언제 어디까지 불어나는지를 먼저 확인하자.

이 후 고슴도치는 물이 어떻게 불어나는지 저장된 지도를 보고 도착지점까지 BFS로 도착하면 된다.

코드로 옮기면 다음과 같다.

요새 STL을 쓰지 않는 연습을 하고 있는지라, 코드가 매우 길다.

#include <stdio.h>
 
typedef struct col {
    int x, y;
}col;
 
col que[10000];
int que_front, que_back;
#define que_size 10000
void que_push(int x, int y) {
    que[que_back] = { x,y };
    que_back = (que_back + 1) % que_size;
}
col que_pop() {
    col tmp = que[que_front];
    que_front = (que_front + 1) % que_size;
 
    return tmp;
}
 
char buf[51];
int r, c;
int map[50][50];
int waters_cnt;
col waters[2500];
col start, dst;
 
int dir[4][2] = { { 1,0 },{ 0,1 },{ -1,0 },{ 0,-1 } };
int abs(int x) {
    return x > 0 ? x : -x;
}
 
void water_bfs() {
    int cnt = 2;
 
    while (que_front != que_back) {
        int size = abs(que_back - que_front);
 
        while (size--) {
            col tmp = que_pop();
 
            for (int i = 0; i < 4; ++i) {
                int xx = tmp.x + dir[i][0];
                int yy = tmp.y + dir[i][1];
 
                if (xx < 0 || yy < 0 || xx >= r || yy >= c)
                    continue;
 
                if (map[xx][yy] != 0)
                    continue;
 
                que_push(xx, yy);
                map[xx][yy] = cnt;
            }
        }
        cnt++;
    }
}
 
int beaber_bfs() {
    int cnt = 2;
 
    while (que_front != que_back) {
        int size = abs(que_front - que_back);
 
        while (size--) {
            col tmp = que_pop();
 
            for (int i = 0; i < 4; ++i) {
                int xx = tmp.x + dir[i][0];
                int yy = tmp.y + dir[i][1];
 
                if (xx < 0 || yy < 0 || xx >= r || yy >= c)
                    continue;
 
                if (xx == dst.x && yy == dst.y)
                    return cnt;
 
                if (map[xx][yy] == 0) {
                    que_push(xx, yy);
                    map[xx][yy] = -1;
                    continue;
                }
 
                if (map[xx][yy] == -1)
                    continue;
 
                if (map[xx][yy] <= cnt)
                    continue;
 
                que_push(xx, yy);
                map[xx][yy] = -1;
            }
        }
 
        cnt++;
    }
    return -1;
}
 
int main() {
    scanf("%d %d", &r, &c);
 
    for (int i = 0; i < r; ++i) {
        scanf("%s", buf);
        for (int j = 0; j < c; ++j) {
            if (buf[j] == '.') // 길
                continue;
            else if (buf[j] == 'D') { // 비버굴
                dst = { i,j };
                map[i][j] = -1;
            }
            else if (buf[j] == 'S') { // 고슴도치
                start = { i,j };
            }
            else if (buf[j] == 'X') // 돌
                map[i][j] = -1;
            else { // 물 
                waters[waters_cnt++] = { i,j };
                map[i][j] = 1;
            }
        }
    }
 
    //물이 번지는 시간 기록
    for (int i = 0; i < waters_cnt; ++i)
        que_push(waters[i].x, waters[i].y);
    water_bfs();
 
 
    map[start.x][start.y] = -1;
    que_push(start.x, start.y);
    
    int ans = beaber_bfs();
    if (ans == -1)
        printf("KAKTUS");
    else
        printf("%d\n", ans - 1);
 
    return 0;
}