C++ 백준 3055번 탈출

[백준 3055번 탈출 문제](https://www.acmicpc.net/problem/3055)

• 물의 번짐과 고슴도치가 움직이는 경로를 모두 BFS 방식으로 풀이하였다.

• 물이 잠길 예정인 곳은 갈 수 없음으로 물의 잠김의 연산을 먼저 실행한 후, 고슴도치의 이동 연산을 하였다.

• 가장 중요한 점은 queue 값의 처음 들어있는 개수만큼의 while문의 반복된 bfs의 계산이라는 것이다.

• 고슴도치가 비버의 굴로 도착하기까지 계속해서 물의 위치와 고슴도치의 위치를 나타내는 queue는 추가되어진다.

• 하지만, 단 한번의 연산(해당 시간:cnt에서 발생되는 경우의 수)이 이루어질 때의 경우만을 연산해야 한다.

• 따라서, while문의 연산을 시작하기 전에 먼저 queue의 값에 들어있는 경우의 수의 값을 알아야 한다. 그만큼의 계산이 그 시간에서 필요로 하는 연산의 수이기 때문이다.

• 각 시간마다의 연산 횟수는 다르다. 고슴도치와 물이 갈 수 있는 방향은 4방향이기 때문에 점점 많아지다가 줄어들게 될 것이다.

• 또한, 물과 고슴도치가 갈 수 있는 지역을 유심히 생각해 보아야 한다.

• 평지 뿐만이 아니라 고슴도치는 'D' 목적지는 물론이고, 물은 평지와도 같은 'S'의 시작점도 갈 수 있다.

   

   

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std; // 물의 번짐함수를 먼저 진행 후 고슴도치 이동.
int R, C, Dx, Dy;
char arr[50][50];
int visit[50][50];
queue<pair<int, int>> w;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
queue<pair<int, int>> s;
bool check(int x, int y)
{
    if (x < 0 || x >= R || y < 0 || y >= C)
        return false;
    return true;
}
void bfs()
{
    while (!s.empty())
    {
        int w_size = w.size(); // 현재 있는 개수만큼만 즉, 현재의 연산으로 큐에 들어간 값은 연산하지 이번에 연산하지 않는다.
        while (w_size--)
        {
            int x = w.front().first;
            int y = w.front().second;
            w.pop();
            for (int i = 0; i < 4; i++)
            {
                int mx = x + dx[i];
                int my = y + dy[i];
                if (check(mx, my) && (arr[mx][my] == '.' || arr[mx][my] == 'S')) // 물이 갈 수 있는 곳 - S 역시 '.'와 같이 비어있는 곳
                {
                    arr[mx][my] = '*';
                    w.push({mx, my});
                }
            }
        }
        int s_size = s.size(); // 한마리의 고슴도치가 4방향으로 이동하므로 cnt의 시간동안 갈 수 있는 모든 경우를 계산한다.
        while (s_size--)
        {
            int x = s.front().first;
            int y = s.front().second;
            s.pop();
            if (x == Dx && y == Dy)
            {
                cout << visit[x][y] - 1
                     << '\n';
                return;
            }
            for (int i = 0; i < 4; i++)
            {
                int mx = x + dx[i];
                int my = y + dy[i];
                if (check(mx, my) && (arr[mx][my] == '.' || arr[mx][my] == 'D') && visit[mx][my] == 0) // 고슴도치가 갈 수 있는 평지(.)와 목적지(D)
                {
                    visit[mx][my] = visit[x][y] + 1;
                    s.push({mx, my});
                }
            }
        }
    }
    cout << "KAKTUS" << '\n';
}
int main()
{
    cin >> R >> C;
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            cin >> arr[i][j];
            if (arr[i][j] == 'S')
            {
                s.push({i, j});
                visit[i][j] = 1;
            }
            else if (arr[i][j] == '*')
                w.push({i, j});
            else if (arr[i][j] == 'D')
                Dx = i, Dy = j;
        }
    }
    bfs();
    return 0;
}