[백준] 3055 :: 탈출

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

3055번: 탈출

 

해결방법

1. 비버의굴과 바위는 못가는 곳으로 표현한다

2. 물이 위치하는 곳에서 부터 bfs를 탐색해, 어떤 지점에 몇초만에 그 물이 도달하는지를 계산해 놓는다 .

예를들어 두번째 예제 같은 경우

3 3

D . *

. . .

. . S

이 경우 물이 차는 속도는 

X 2 1

4 3 2

5 4 3 이 된다. 

단, 이 것을 구할때 물이 한곳도 없는 경우가 존재하므로 초기값은 0이 아닌 INF로 두는것이 편리하다. 

3. 이제 고슴도치를 이동시킨다. 고슴도치의 최단 이동경로를 구하면 되는데, 고슴도치가 이동할 수 있는 경우는 자신의 위치에서 상하좌우로 인접한 한 칸임과 동시에 물이 이동하는 속도보다 느려야 한다. 즉 x,y로 이동할 때 물이 그곳에 2 만에 도달한다면 고슴도치는 그 칸으로가는 최단경로가 2보다 작아야만 이동할 수 있는 것이다.

 

 

 

소스보기

#include <iostream>
#include <queue>
using namespace std;
#define INF 987654321
int n, m;
int map[51][51];
int sX, sY;//고슴도치 위치
int endX, endY;//끝나는 지점
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int d[51][51];
int main() {
    cin >> n >> m;
    queue<pair<int, int> > q;//물 bfs용 큐
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char c;
            cin >> c;
            if (c == 'D') {
                map[i][j] = -1;//바위는 -1로 표현
                endX = i; endY = j;
            }
            else if (c == 'S') {
                sX = i; sY = j;
                map[i][j] = INF;
            }
            else if (c == '*') {
                q.push({ i,j });
                map[i][j] = 1;
            }
            else if (c == 'X') {
                map[i][j] = -1;
            }
            else
                map[i][j] = INF;
        }
    }
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        int dist = map[x][y];
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nX = x + dx[i];
            int nY = y + dy[i];
            if (nX < 0 || nX >= n || nY < 0 || nY >= m) continue;
            if (map[nX][nY] == INF) {
                map[nX][nY] = dist + 1;
                q.push({ nX, nY });
            }
        }
    }//여기까지 물이 이동하는 거리 계산함
 
    q.push({ sX, sY });
    d[sX][sY] = 1;
    map[endX][endY] = 987654321;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        int dist = d[x][y];
        if (x == endX && y == endY)
            break;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nX = x + dx[i];
            int nY = y + dy[i];
            if (nX < 0 || nX >= n || nY < 0 || nY >= m) continue;
            if ((dist + 1) < map[nX][nY] && d[nX][nY] == 0) {
                d[nX][nY] = dist + 1;
                q.push({ nX, nY });            
            }
        }
 
    }
 
    int ans = d[endX][endY];
    if (ans != 0)
        cout << ans-1 << endl;
    else
        cout << "KAKTUS" << endl;
    
}