[알고리즘 문제] 백준3055 - 탈출

www.acmicpc.net/problem/3055

3055번: 탈출

물을 먼저 퍼뜨리고 이후에 고슴도치를 움직이는 방식으로 풀 수 있습니다. 그리고 고슴도치의 중복동선과 최단시간은 visited[][]로 관리할 수 있습니다. 전형적인 bfs문제입니다.

 

#include <iostream>
#include <queue>

using namespace std;

int height, width;
pair<int, int> des, start;
queue<pair<int, int>> mole, water;
int visited[50][50];
string map[50];

int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

int bfs()
{

    visited[start.first][start.second] = 0;
    mole.push(start);

    while (!mole.empty())
    {
        int waterSize = water.size();
        for (int i = 0; i < water.size(); i++) // 먼저 물을 퍼뜨림
        {
            int y = water.front().first;
            int x = water.front().second;
            water.pop();

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

                if (newX < 0 || newY < 0 || newX >= width || newY >= height)
                {
                    continue;
                }
                if (map[newY][newX] == '.')
                {
                    map[newY][newX] = '*';
                    water.push({newY, newX});
                }
            }
        }

        int moleSize = mole.size();
        for (int i = 0; i < moleSize; i++) // 고슴도치 움직임
        {
            int y = mole.front().first;
            int x = mole.front().second;
            mole.pop();

            if (y == des.first && x == des.second)
            {
                return visited[y][x];
            }

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

                if (newX < 0 || newY < 0 || newX >= width || newY >= height)
                {
                    continue;
                }

                if (map[newY][newX] != 'X' && map[newY][newX] != '*' && !visited[newY][newX])
                {
                    mole.push({newY, newX});
                    visited[newY][newX] = visited[y][x] + 1;
                }
            }
        }
    }
    return -1;
}

int main()
{
    cin >> height >> width;

    for (int y = 0; y < height; y++)
    {
        cin >> map[y];
        for (int x = 0; x < map[y].length(); x++)
        {
            if (map[y][x] == 'D')
            {
                des.first = y;
                des.second = x;
            }
            else if (map[y][x] == 'S')
            {
                start.first = y;
                start.second = x;
            }
            else if (map[y][x] == '*')
            {
                water.push({y, x});
            }
        }
    }

    int ans = bfs();

    if (ans == -1)
    {
        cout << "KAKTUS" << endl;
    }
    else
    {
        cout << ans << endl;
    }
    return 0;
}