백준 / 1888 / 곰팡이 / C++

문제 링크 : https://www.acmicpc.net/problem/1888

#include <bits/stdc++.h>

using namespace std;

int n, m;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

bool check(vector<vector<int>> &arr)
{
    int checktmp = 0;
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (arr[i][j] == 0 || visited[i][j])
            {
                continue;
            }
            checktmp++;
            queue<pair<int, int>> Q;
            Q.push({i, j});
            visited[i][j] = true;
            while (!Q.empty())
            {
                pair<int, int> cur = Q.front();
                Q.pop();
                for (int k = 0; k < 4; k++)
                {
                    int nx = cur.first + dx[k];
                    int ny = cur.second + dy[k];
                    if (nx < 0 || ny < 0 || nx >= n || ny >= m || visited[nx][ny] || arr[nx][ny] == 0)
                    {
                        continue;
                    }
                    visited[nx][ny] = true;
                    Q.push({nx, ny});
                }
            }
        }
    }
    return checktmp == 1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("test.txt", "rt", stdin);
    cin >> n >> m;
    vector<vector<int>> arr(n, vector<int>(m));
    queue<pair<int, int>> Q;
    for (int i = 0; i < n; i++)
    {
        string tmp;
        cin >> tmp;
        for (int j = 0; j < m; j++)
        {
            arr[i][j] = tmp[j] - '0';
            if (arr[i][j] != 0)
            {
                Q.push({i, j});
            }
        }
    }
    int ans = 0;
    while (1)
    {
        if (check(arr))
        {
            break;
        }
        vector<vector<int>> next_arr = arr;
        int size = Q.size();
        while (size--)
        {
            pair<int, int> cur = Q.front();
            Q.pop();
            int speed = arr[cur.first][cur.second];
            for (int i = cur.first - speed; i <= cur.first + speed; i++)
            {
                for (int j = cur.second - speed; j <= cur.second + speed; j++)
                {
                    if (i < 0 || j < 0 || i >= n || j >= m)
                    {
                        continue;
                    }
                    if (next_arr[i][j] < arr[cur.first][cur.second])
                    {
                        next_arr[i][j] = arr[cur.first][cur.second];
                        Q.push({i, j});
                    }
                }
            }
        }
        arr = next_arr;
        ans++;
    }

    cout << ans;
    return 0;
}

bfs 탐색 문제다. 곰팡이의 좌표를 기준으로 속도에 따라 번지는 양을 구현해야 하는데 생각보다 구현이 어렵진 않았다.

단지 처음 시도에는 원본 그래프 arr에 실시간으로 곰팡이를 갱신했는데, 그러면 원래 갱신해야하는 부분에 덮어씌우는 과정에서 누락되는 값이 발생한다는 사실을 몰라 한번 WA를 받았다. 임시 배열 next_arr을 선언해 next_arr을 arr에 한번에 덮어씌우는 방식으로 AC를 받았다.