3055번

3055번 - 탈출

풀기전에 나름 쉬운문제라고 생각했는데, 여러 가지 명시해주지 않은 조건을 간과해서 수정을 여러번 했다.

일단 생각한 로직은

첫번째로 BFS를 통해서 물이 갈 수 있는 최단거리를 저장한다. 이때, D 나 X에는 갈 수 없다.

두번째로, BFS를 통해 비버가 갈 수 있는 최단거리를 저장한다. 이때, X 나 * 에는 갈 수 없다.

또한 비버는 물이 갈 수있는 시간보다 빠를때에만 그 칸으로 이동할 수 있다. 물과 같은 시간이나 그 이상 시간에 오면 물이 범람한다.

물이 갈 수 있는 경로는 초기값은 INF로 설정하고, 비버가 갈 수 있는 경로는 -1로 설정한다.

왜냐하면 물이 갈 수 없는 곳, X를 제외하고는 비버가 무조건 갈 수 있게 하기 위함이다. 또한 물이 여러곳에서 올 경우 , 최소거리를

구하는데 약간 편리해진다.

##내가 실수 했던 점

내가 실수 했던 점은, 물이 꼭 1군데에서만 온다고 생각했다. 문제의 조건에서는 S,D 가 1개씩 꼭 있다고 했을 뿐,

*가 1개라는 말은 하지 않았는데, 머리속으로 그냥 풀다보니 계속 쳇바퀴를 돌았다.

<정답 코드>

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
typedef vector<vector<char>> vc;
typedef vector<vector<int>> vv;
const int INF = 987654321;
int main()
{
    //freopen("input.txt", "r", stdin);
    int n, m;
    scanf("%d%d", &n, &m);
    vc map(n, vector<char>(m));
 
    queue<pair<int, int>> q;
    vv water(n, vector<int>(m, INF));
 
    int bx=-1, by=-1, wx = -1, wy = -1, gx = -1, gy = -1;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> map[i][j];
 
            if (map[i][j] == 'S')
            {
                bx = i, by = j;
            }
            if (map[i][j] == '*')
            {
                q.push({ i,j });
                water[i][j] = 1;
            }
            if (map[i][j] == 'D')
            {
                gx = i, gy = j;
            }
        }
    }
 
 
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int d = 0; d < 4; d++)
        {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (nx >= 0 && ny >= 0 && nx < n && ny < m && water[nx][ny]>water[x][y]+1 && map[nx][ny] != 'D' && map[nx][ny] != 'X')
            {
 
                water[nx][ny] = water[x][y] + 1;
 
                q.push({ nx,ny });
            }
        }
    }
    
 
    queue<pair<int, int>> q2;
    vv bever(n, vector<int>(m, -1));
    q2.push({ bx, by });
    bever[bx][by] = 1;
 
    int size;
    int depth = 0;
 
    while (!q2.empty())
    {
        size = q2.size();
        depth++;
        for (int i = 0; i < size; i++)
        {
            int x = q2.front().first;
            int y = q2.front().second;
            q2.pop();
 
            for (int d = 0; d < 4; d++)
            {
                int nx = x + dx[d];
                int ny = y + dy[d];
                if (nx >= 0 && ny >= 0 && nx < n && ny < m && bever[nx][ny] == -1 && depth+1<water[nx][ny] && map[nx][ny]!='*' && map[nx][ny]!='X')
                {
                    if (nx == gx && ny == gy)
                    {
                        printf("%d\n", depth);
                        return 0;
                    }
                    bever[nx][ny] = bever[x][y] + 1;
                    q2.push({ nx,ny });
                }
            }
        }
    }
 
 
    printf("KAKTUS\n");
    return 0;
}