[ 백준 16431 ] 베시와 데이지 (C++)

백준의 베시와 데이지(16431) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 베시와 데이지 두 소 모두 존에게 갈 최단 경로만 구하면 되기 때문에 본인은 너비우선탐색(BFS)를 이용해서 접근해

   보았다.

   베시가 존에게 가는데 걸리는 최소시간을 구하는 BFS 와 데이지가 존에게 가는데 걸리는 최소시간을 구하는 BFS,

   총 2번의 BFS탐색을 진행해서 걸린 시간을 비교해주었다.

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<cstring>
 
#define endl "\n"
#define MAX 1010
using namespace std;
 
pair<int, int> Bessy, Daisy, John;
bool Visit[MAX][MAX];
 
int Bdx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int Bdy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
int Ddx[] = { 0, 0, 1, -1 };
int Ddy[] = { 1, -1, 0, 0 };
 
void Input()
{
    cin >> Bessy.first >> Bessy.second;
    cin >> Daisy.first >> Daisy.second;
    cin >> John.first >> John.second;
}
 
int BFS(int a, int b, int Idx)
{
    memset(Visit, false, sizeof(Visit));
    queue<pair<pair<int, int>, int>> Q;
    Q.push(make_pair(make_pair(a, b), 0));
    Visit[a][b] = 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 == John.first && y == John.second) return Cnt;
 
        if (Idx == 0)
        {
            for (int i = 0; i < 8; i++)
            {
                int nx = x + Bdx[i];
                int ny = y + Bdy[i];
                if (nx >= 0 && ny >= 0 && nx < 1001 && ny < 1001)
                {
                    if (Visit[nx][ny] == false)
                    {
                        Visit[nx][ny] = true;
                        Q.push(make_pair(make_pair(nx, ny), Cnt + 1));
                    }
                }
            }
        }
        else
        {
            for (int i = 0; i < 4; i++)
            {
                int nx = x + Ddx[i];
                int ny = y + Ddy[i];
                if (nx >= 0 && ny >= 0 && nx < 1001 && ny < 1001)
                {
                    if (Visit[nx][ny] == false)
                    {
                        Visit[nx][ny] = true;
                        Q.push(make_pair(make_pair(nx, ny), Cnt + 1));
                    }
                }
            }
        }
    }
}
 
void Solution()
{
    int Res = BFS(Bessy.first, Bessy.second, 0);
    int Res2 = BFS(Daisy.first, Daisy.second, 1);
 
    if (Res > Res2) cout << "daisy" << endl;
    else if (Res < Res2) cout << "bessie" << endl;
    else cout << "tie" << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}