[BOJ] 3055번: 탈출

3055번: 탈출

BFS로 풀 수 있다.

주의해야 할 점은 물이 흐르는 것을 계산할 때 임시 배열에 변경 사항을 저장했다가 실제 배열에 적용시켜줘야 물이 정상적으로 흐르는 것을 계산할 수 있다.

코드

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

int R, C;
const int dx[] = {0, 0, 1, -1}, dy[] = {-1, 1, 0, 0};
char map[51][51];
bool visit[51][51];
pair<int, int> D, S;

inline bool safe(int y, int x)
{
    return (0 <= y && y < R && 0 <= x && x < C);
}

inline bool chkSum(int y, int x)
{
    return safe(y, x) && !visit[y][x] && (map[y][x] == '.' || map[y][x] == 'D');
}

void waterflow()
{
    int memo[51][51];
    memset(memo, 0, sizeof memo);
    for (int i = 0; i < R; ++i)
    {
        for (int j = 0; j < C; ++j)
        {
            if (map[i][j] == '*')
            {
                for (int k = 0; k < 4; ++k)
                {
                    int nextY = i + dy[k];
                    int nextX = j + dx[k];

                    if (safe(nextY, nextX) && map[nextY][nextX] != 'D' && map[nextY][nextX] != 'X')
                    {
                        memo[nextY][nextX] = '*';
                    }
                }
            }
        }
    }
    for (int i = 0; i < R; ++i)
    {
        for (int j = 0; j < C; ++j)
        {
            if (memo[i][j] == '*')
                map[i][j] = '*';
        }
    }
}

int BFS(int y, int x)
{
    int count = 1;
    queue<pair<int, int>> q;
    q.push(make_pair(y, x));
    visit[y][x] = true;

    while (!q.empty())
    {
        int size = q.size();
        waterflow();
        while (size--)
        {
            int tY = q.front().first;
            int tX = q.front().second;
            q.pop();
            for (int i = 0; i < 4; ++i)
            {
                int nextY = tY + dy[i];
                int nextX = tX + dx[i];

                if (chkSum(nextY, nextX))
                {
                    if (nextY == D.first && nextX == D.second)
                        return count;
                    visit[nextY][nextX] = true;
                    map[nextY][nextX] = 'S';
                    q.push(make_pair(nextY, nextX));
                }
            }
        }
        ++count;
    }
    return -1;
}

int main()
{
    scanf("%d %d", &R, &C);
    for (int i = 0; i < R; ++i)
    {
        for (int j = 0; j < C; ++j)
        {
            scanf(" %c", &map[i][j]);
            if (map[i][j] == 'S')
                S = make_pair(i, j);
            else if (map[i][j] == 'D')
                D = make_pair(i, j);
        }
    }

    int ans = BFS(S.first, S.second);

    if (ans == -1)
        printf("KAKTUS\n");
    else
        printf("%d\n", ans);

    return 0;
}