[ 백준 17086 ] 아기상어2 (C++)

백준의 아기상어2(17086) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 문제를 간단하게 요약해보자면, 아기상어가 없는 빈 칸에서 가장 가까운 아기상어 까지 가는데 걸리는 칸 수의 최댓값을

   구하는 문제이다.

   본인은 입력과 동시에 빈 칸의 좌표들을 Vector에 저장해 주었고, 각각의 좌표들을 시작점으로 BFS탐색을 돌려서

   가장 가까운 아기상어를 찾는 식으로 구현하였다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
 
#define endl "\n"
#define MAX 50
using namespace std;
 
int N, M, Answer;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
vector<pair<int, int>> V;
 
int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
 
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] == 0)
            {
                V.push_back(make_pair(i, j));
            }
        }
    }
}
 
int BFS(int a, int b)
{
    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 (MAP[x][y] == 1) return Cnt;
        
        for (int i = 0; i < 8; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < N && ny < M)
            {
                if (Visit[nx][ny] == false)
                {
                    Visit[nx][ny] = true;
                    Q.push(make_pair(make_pair(nx, ny), Cnt + 1));
                }
            }
        }
    }
}
 
void Solution()
{
    for (int i = 0; i < V.size(); i++)
    {
        memset(Visit, false, sizeof(Visit));
        int x = V[i].first;
        int y = V[i].second;
 
        int Temp = BFS(x, y);
        if (Temp > Answer) Answer = Temp;
    }
}
 
void Solve()
{
    Input();
    Solution();
    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;
}