[백준] 7576번

bfs 문제다.

이제 bfs는 쉽게 코딩이 된다

시간복잡도는 O(n)인데 실상은 2(n*m) + k다

k는 1근처 0들의 갯수다.

즉, k는 최대 n*m이다.

따라서 최악ㄷ은 3(n*m)이고 O(n)으로 볼 수 있다.

#include <iostream>
#include <vector>
#include <queue>
#include <map>


int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<int>> box(m+2, std::vector<int>(n+2, -1));
    std::queue<std::pair<int, int>> q;
    std::map<std::pair<int, int>, bool> visited;
    for (int i = 1; i < m+1; i++) {
        for (int j = 1; j < n+1; j++) {
            std::cin >> box[i][j];
            if (box[i][j] == 1) {
                q.push(std::make_pair(i, j));
                visited[{i, j}] = true;
            }
        }
    }
    int count = 0;
    while (!q.empty()) {
        std::pair<int, int> current = q.front(); q.pop();

        if (box[current.first+1][current.second] == 0 && visited.find({current.first+1, current.second}) == visited.end()) {
            q.push(std::make_pair(current.first+1, current.second));
            visited[{current.first+1, current.second}] = true;
            box[current.first+1][current.second] = box[current.first][current.second] + 1;
        }
        if (box[current.first-1][current.second] == 0 && visited.find({current.first-1, current.second}) == visited.end()) {
            q.push(std::make_pair(current.first-1, current.second));
            visited[{current.first-1, current.second}] = true;
            box[current.first-1][current.second] = box[current.first][current.second] + 1;
        }
        if (box[current.first][current.second+1] == 0 && visited.find({current.first, current.second+1}) == visited.end()) {
            q.push(std::make_pair(current.first, current.second+1));
            visited[{current.first, current.second+1}] = true;
            box[current.first][current.second+1] = box[current.first][current.second] + 1;
        }
        if (box[current.first][current.second-1] == 0 && visited.find({current.first, current.second-1}) == visited.end()) {
            q.push(std::make_pair(current.first, current.second-1));
            visited[{current.first, current.second-1}] = true;
            box[current.first][current.second-1] = box[current.first][current.second] + 1;
        }
        if (count < box[current.first][current.second]) {
            count = box[current.first][current.second];
        }
    }
    for (int i = 1; i < m+1; i++) {
        for (int j = 1; j < n+1; j++) {
            if (box[i][j] == 0) {
                std::cout << -1;
                return 0;
            }
        }
    }
    std::cout << count-1 << std::endl;

    return 0;
}