[백준 3055] 탈출

[백준 3055] 탈출

문제 링크

#include "header.h"
using namespace std;
int r, c;
char board[51][51];
int water_day[51][51];
int days[51][51];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
queue<pair<int, int>> water_q;
queue<pair<int, int>> q;
pair<int, int> bieber;
void input()
{
    cin >> r >> c;
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            cin >> board[i][j];
            if (board[i][j] == 'S')
            {
                q.push({i, j});
            }
            if (board[i][j] == '*')
                water_q.push({i, j});
            if (board[i][j] == 'D')
                bieber = {i, j};
        }
    }
}
void get_water()
{
    while (!water_q.empty())
    {
        int x = water_q.front().first;
        int y = water_q.front().second;
        water_q.pop();

        for (int j = 0; j < 4; j++)
        {
            int nx = x + dx[j];
            int ny = y + dy[j];

            if (nx >= r || nx < 0 || ny >= c || ny < 0)
                continue;

            if (board[nx][ny] == '.' && water_day[nx][ny] == 0)
            {
                //물 채우기
                water_day[nx][ny] = water_day[x][y] + 1;
                water_q.push({nx, ny});
            }
        }
    }
}
void move_hedgehog()
{
    int cnt = 0;

    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= r || nx < 0 || ny >= c || ny < 0)
                continue;
            if (days[nx][ny] == 0 && (board[nx][ny] == '.' || board[nx][ny] == 'D'))
            {
                if (water_day[nx][ny] == 0 || water_day[nx][ny] > days[x][y] + 1)
                {
                    days[nx][ny] = days[x][y] + 1;
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }
}
void solve()
{
    get_water();
    move_hedgehog();

    if (days[bieber.first][bieber.second] != 0)
    {
        cout << days[bieber.first][bieber.second];
    }
    else
    {
        cout << "KAKTUS";
    }
}
int main()
{
    input();
    solve();
    return 0;
}

• 시뮬레이션 + bfs 문제.
• bieber(이제 찾아보니 beaver가 맞다..ㅋㅋㅋㅋㅋㅋㅋㅋㅋ)가 아닌 r-1, c-1을 출력해서 계속해서 틀렸다고 나왔다. 어이없는 실수..
• 물을 하루씩 늘려주면서 언제 채워지는지 bfs로 저장 해 주고,
• 고슴도치를 움직일 때마다 저장된 물과 비교해주면서, 다음날 물이 채워지지 않는 곳만 탐색한다.
• water_days가 0일 경우 -> 물이 침범하지 못하는 곳이거나, 답이기 때문에 넣어줘야 한다.