[백준 3055번] 탈출

풀이

---

BFS로 풀면 되지만 조건 중에 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다고 되어있기 대문에 고슴도치의 이동보다 물의 이동이 항상 1만큼 빨라야한다.

그래서 BFS를 돌때 물을 먼저 1칸 이동후 고슴도치를 이동시키면 해결할 수 있다.

소스코드

---

#include <iostream>
using namespace std;
 
int se, ga;
char map[51][51];
int pos, des;
int que[10001], waterque[501][10001], posvisit[51][51] = { 0, }, watervisit[51][51] = { 0, };
int h, t, wh[501], wt[501];
 
void push(int a) {
    que[t++] = a;
}
int pop() {
    return que[h++];
}
void wpush(int cnt, int a) {
    waterque[cnt][wt[cnt]++] = a;
}
int wpop(int cnt) {
    return waterque[cnt][wh[cnt]++];
}
 
void wateroneHour(int hour) { // 함수 호출 1회당 물도 1칸 이동 
    while (wh[hour] != wt[hour]) {
        int wpos = wpop(hour);
        int wx = wpos / 1000;
        int wy = wpos % 1000;
 
        if (wx + 1 <= se - 1 && watervisit[wx + 1][wy] == 0 && map[wx+1][wy]=='.') {  // 아래
            watervisit[wx + 1][wy] = 1;
            map[wx + 1][wy] = '*';
            wpush(hour + 1, (wx + 1) * 1000 + wy);
        }
        if (wx - 1 >= 0 && watervisit[wx - 1][wy] == 0 && map[wx - 1][wy] == '.') { // 위
            watervisit[wx - 1][wy] = 1;
            map[wx - 1][wy] = '*';
            wpush(hour + 1, (wx - 1) * 1000 + wy);
        }
        if (wy + 1 <= ga - 1 && watervisit[wx][wy + 1] == 0 && map[wx][wy + 1] == '.') { // 오른쪽
            watervisit[wx][wy+1] = 1;
            map[wx][wy+1] = '*';
            wpush(hour + 1, wx * 1000 + wy+1);
        }
        if (wy - 1 >= 0 && watervisit[wx][wy - 1] == 0 && map[wx][wy - 1] == '.') { // 왼쪽
            watervisit[wx][wy - 1] = 1;
            map[wx][wy - 1] = '*';
            wpush(hour + 1, wx * 1000 + wy-1);
        }
    }
}
 
void bfs() {
    while (1) {
        int pos = pop();
        int x = pos / 1000;
        int y = pos % 1000;
 
        wateroneHour(posvisit[x][y] - 3);
 
        if ((x + 1 <= se - 1 && map[x + 1][y] == 'D') || (x - 1 >= 0 && map[x - 1][y] == 'D') || (y + 1 <= ga - 1 && map[x][y + 1] == 'D') || (y - 1 >= 0 && map[x][y - 1] == 'D')) {
            cout << posvisit[x][y] -2 << '\n';
            return;
        }
 
        if (x + 1 <= se - 1 && posvisit[x + 1][y] == 0 && map[x + 1][y] == '.') {
            posvisit[x + 1][y] = posvisit[x][y]+1;
            push((x + 1) * 1000 + y);
        }
        if (x - 1 >= 0 && posvisit[x - 1][y] == 0 && map[x - 1][y] == '.') {
            posvisit[x - 1][y] = posvisit[x][y] + 1;
            push((x - 1) * 1000 + y);
        }
        if (y + 1 <= ga - 1 && posvisit[x][y+1] == 0 && map[x][y+1] == '.') {
            posvisit[x][y + 1] = posvisit[x][y] + 1;
            push(x * 1000 + y + 1);
        }
        if (y - 1 >= 0 && posvisit[x][y - 1] == 0 && map[x][y - 1] == '.') {
            posvisit[x][y - 1] = posvisit[x][y] + 1;
            push(x * 1000 + y - 1);
        }
        if (h == t) {
            cout << "KAKTUS" << '\n';
            break;
        }
    }
}
 
int main() {
    cin >> se >> ga;
    for (int i = 0; i < se; i++) {
        for (int j = 0; j < ga; j++) {
            cin >> map[i][j];
            if (map[i][j] == 'D')  // 비버굴 위치
                des = 1000 * i + j;
            else if (map[i][j] == 'S') // 고슴도치 위치
                pos = 1000 * i + j;
            else if (map[i][j] == '*') // 물 위치
                wpush(0, 1000*i + j);
        }
    }
 
    posvisit[pos / 1000][pos % 1000] = 3;
    push(pos);
    bfs();
 
    return 0;
}