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

17086번 : 아기 상어 2

---

문제)

N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다.

어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.

안전 거리가 가장 큰 칸을 구해보자. 

 

 

 

입력 :

첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 주어진다.

 

 

출력 :

첫째 줄에 안전 거리의 최댓값을 출력한다.

 

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
int n, m;
vector<vector<int>> vec;
vector<vector<int>> visited;
 
vector<pair<int, int>> sharks;
 
int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
 
void bfs(int a, int b, int t)
{
    queue<pair<int, int>> q;
    q.push(make_pair(a, b));
    visited[a][b] = 1;
 
    int cnt = 1;
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int i = 0; i < 8; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (0 > nx || nx >= n) continue;
            if (0 > ny || ny >= m) continue;
 
            if (visited[nx][ny] == 0)
            {
                visited[nx][ny] = visited[x][y] + 1;
                q.push(make_pair(nx, ny));
            }
            else if (visited[nx][ny] > visited[x][y] + 1)
            {
                visited[nx][ny] = visited[x][y] + 1;
                q.push(make_pair(nx, ny));
            }
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
 
    vec.resize(n, vector<int>(m, 0));
    visited.resize(n, vector<int>(m, 0));
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> vec[i][j];
            if (vec[i][j] == 1) sharks.push_back(make_pair(i, j));
        }
    }
 
    for (int i = 0; i < sharks.size(); i++)
    {
        bfs(sharks[i].first, sharks[i].second, i);
    }
 
    int result = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            result = max(result, visited[i][j]);
        }
    }
 
    cout << result - 1;
 
 
    
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/17086 

17086번: 아기 상어 2