[Algorithm] Baekjoon 3055번 : 탈출

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

3055번: 탈출

struct Node
{
    int y;
    int x;
    bool isWater;
    int count;
};
 
int n, m;
char arr[50][50];
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
Node start;
vector<Node> waters;
 
bool checkInRange(int y, int x)
{
    if (y < 0 || y >= n || x < 0 || x >= m) return false;
    return true;
}
 
int BFS()
{
    queue<Node> q;
 
    for (int i = 0; i < waters.size(); ++i)
    {
        q.push(waters[i]);
    }
 
    q.push(start);
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        int curIsWater = q.front().isWater;
        int curCount = q.front().count;
        q.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (!checkInRange(nextY, nextX)) continue;
            if (curIsWater)
            {
                if (arr[nextY][nextX] == 'S' || arr[nextY][nextX] == '.')
                {
                    arr[nextY][nextX] = '*';
                    q.push({ nextY,nextX,true,0 });
                }
            }
            else
            {
                if (arr[nextY][nextX] == '.')
                {
                    arr[nextY][nextX] = 'S';
                    q.push({ nextY,nextX,false,curCount + 1 });
                }
                else if (arr[nextY][nextX] == 'D')
                {
                    return curCount + 1;
                }
            }
        }
    }
    return -1;
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            cin >> arr[i][j];
            if (arr[i][j] == '*')
            {
                waters.push_back({ i,j,true,0 });
            }
            else if (arr[i][j] == 'S')
            {
                start = { i,j,false,0 };
            }
        }
    }
 
    int result = BFS();
 
    if (result == -1) cout << "KAKTUS";
    else cout << result;
}

어렵지않긴한데, 관련유형을 많이 안풀어봤다면 살짝 고민할 수도 있다.

물이 차오를 예정인곳에는 고슴도치가 못간다는 조건만 잘 해결하면 된다.

이걸 쉽게 생각하면, 그냥 물을 먼저 퍼뜨리면 된다. 

그다음에 고슴도치차례때 그냥 물이있는 칸을 안가면 그만이다.

반복하다가 고슴도치차례때 다음칸이 목표지면 바로 return시키면 끝.