백준 17086 아기 상어 2

문제 설명

17086 아기상어2 문제 링크

문제 풀이

전형적인 bfs 라서 풀이를 작성하지 않으려 했는데 동아리에서 풀이를 공유하다가 좋은 풀이가 있어서 두가지 풀이를 작성해보려고 한다.

1번 풀이는 아래 소스 코드의 풀이다.
1단계 첫 번째 아기상어에서 출발해서 빈 공간에 거리를 채운다.
2단계 두 번째 아기상어에서 출발해서 가까운 칸부터 첫 번째 상어가 적어둔 거리보다 가까우면 업데이트 한다.
3단계 ~ 상어 수만큼 반복한다.

2번 풀이는 따로 코드를 작성하지는 않았는데 풀이의 아이디어를 그림으로 표현하면 다음과 같다.
1단계 큐에 담겨있는 모든 상어에서 거리가 2인 칸을 채운다.
2단계 2가 채워진 칸이 큐에 담겨있기 때문에 큐에서 하나씩 꺼내서 3인 칸을 채운다.
3단계 이제 3이 채워진 칸이 큐에 담겨있을 것이다. 이 칸을 하나씩 꺼내서 다음칸을 탐색하는데 거리가 4인 칸이 없기 때문에 더 이상 큐에 담기는 칸이 없다.

소스 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> res(n, vector<int>(m, 0));
    queue<pair<int, int>> que;
    int tmp;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> tmp;
            if (tmp == 1) {
                que.push(make_pair(i, j));
                res[i][j] = 1;
            }
        }
    }
    int di[] = {-1, 1, 0, 0, -1, -1, 1, 1};
    int dj[] = {0, 0, -1, 1, -1, 1, -1, 1};
    while (!que.empty()) {
        int i = que.front().first;
        int j = que.front().second;
        que.pop();
        for (int k = 0; k < 8; k++) {
            int ni = i + di[k];
            int nj = j + dj[k];
            if (ni < 0 || nj < 0 || ni >= n || nj >= m) {
                continue;
            }
            if (res[ni][nj] == 0) {
                res[ni][nj] = res[i][j] + 1;
                que.push(make_pair(ni, nj));
            } else if (res[ni][nj] > res[i][j] + 1) {
                res[ni][nj] = res[i][j] + 1;
                que.push(make_pair(ni, nj));
            }
        }
    }
    int max = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (res[i][j] > max) {
                max = res[i][j];
            }
        }
    }
    cout << max - 1;

    return 0;
}