[ SWEA 7793 ] 오! 나의 여신님 (C++)

SWExpertAcademy의 오 ! 나의 여신님(7793 / D5) 문제이다.

[ 문제풀이 ]

현재 수연이가 위치한 곳에서, 악마의 손아귀 영역을 피해서 여신님께 갈 수 있는 최소시간을 구해야 하는 문제이다.

본인은 이 문제를 너비우선탐색(BFS) 방법을 이용해서 접근해보았는데, 총 2번의 BFS를 사용해 주었다.

첫 번째 BFS는 '악마들의 맵'을 생성하기 위해서 사용한 BFS이다.

초기에 악마가 존재하는 좌표들을 시작점으로, 모든 좌표에 악마의 손아귀가 퍼질 수 있는 최소시간을 구해서 저장하는

' 악마들의 맵'을 생성해주었다.

그 이후, 수연이를 BFS탐색을 통해서 여신님께 갈 수 있는지 판단해 주었다.

수연이의 BFS에서는 미리 만들어둔 악마들의 맵과 시간을 비교해가면서 이동하려는 좌표에 갈 수 있는지 없는지를

판단해주면서 구해주었다.

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<string>
 
#define endl "\n"
#define MAX 50
#define INF 987654321
using namespace std;
 
int N, M, Answer;
char MAP[MAX][MAX];
int Devil_MAP[MAX][MAX];
bool Visit[MAX][MAX];
vector<pair<int, int>> Devil;
pair<int, int> Start, End;
string GameOver = "GAME OVER";
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Initialize()
{
    memset(Visit, false, sizeof(Visit));
    Devil.clear();
    for (int i = 0; i < MAX; i++)
    {
        for(int j = 0 ; j < MAX; j++)
        { 
            Devil_MAP[i][j] = INF;
        }
    }
}
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == 'S')
            {
                Start.first = i;
                Start.second = j;
            }
            else if (MAP[i][j] == 'D')
            {
                End.first = i;
                End.second = j;
            }
            else if (MAP[i][j] == '*') Devil.push_back(make_pair(i, j));
        }
    }
}
 
void Make_Devil_MAP()
{
    queue<pair<int, int>> Q;
    for(int i = 0 ; i < Devil.size(); i++)
    { 
        int x = Devil[i].first;
        int y = Devil[i].second;
        Q.push(make_pair(x, y));
        Devil_MAP[x][y] = 0;        
    }
 
    while (Q.empty() == 0)
    {
        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 >= 0 && ny >= 0 && nx < N && ny < M)
            {
                if (MAP[nx][ny] == 'X') continue;
                if (MAP[nx][ny] == 'D') continue;
 
                if (Devil_MAP[nx][ny] > Devil_MAP[x][y] + 1)
                {
                    Devil_MAP[nx][ny] = Devil_MAP[x][y] + 1;
                    Q.push(make_pair(nx, ny));
                }
            }
        }
    }
}
 
int Move()
{
    queue<pair<pair<int, int>, int>> Q;
    Q.push(make_pair(make_pair(Start.first, Start.second), 0));
    Visit[Start.first][Start.second] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int Cnt = Q.front().second;
        Q.pop();
 
        if (x == End.first && y == End.second) return Cnt;
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < N && ny < M)
            {
                if (MAP[nx][ny] == 'X') continue;
                if (Visit[nx][ny] == true) continue;
 
                if (Devil_MAP[nx][ny] > Cnt + 1)
                {
                    Visit[nx][ny] = true;
                    Q.push(make_pair(make_pair(nx, ny), Cnt + 1));
                }
            }
        }
    }
    return -1;
}
 
void Solution()
{
    Make_Devil_MAP();
    Answer = Move();
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " ";
        if (Answer == -1) cout << GameOver << endl;
        else cout << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}