[BOJ] C++ 2573 빙산 - BFS, 시간 복잡도 잘 계산하기

2573번: 빙산

예제

5 7
0 0 0 0 0 0 0
0 2 4 5 3 0 0
0 3 0 2 5 2 0
0 7 6 2 4 0 0
0 0 0 0 0 0 0

ans : 2

---

가장 먼저 떠올릴 수 있는 풀이는 1년 후 빙산의 형태로 바꾸고 바꿀 때마다 BFS를 돌리는 방법이다. 이 방식으로 했을 때 구현은 쉬워 보이지만 시간 복잡도가 문제가 된다. 위의 방식대로 시간 복잡도를 계산해 보자. 최대 300 * 300 크기의 배열에 빙산이 높이 10까지 있을 수 있다. 300 * 300 칸에 모두 빙산이 10까지 가득 차있다면, 정말 러프하게 계산해도 O(N * M * year) 만큼의 시간이 걸린다. 예전에 공부하면서 대략 10억 번의 연산이 1초인걸 감안하면 위의 방식으로 구현해도 된다. 시간복잡도 이론상으로 시간 초과가 괜찮다면 최대한 최적화를 하면서 구현해 보고 틀렸다면 다른 방식을 생각해 보기로 했다. 

[문제풀이] int, long long 오버플로우, 시간초과 관련 미세 팁

 

1년 후의 빙산을 업데이트하는 함수부터 짜보자. int zero [MAX][MAX] 배열을 만들어서 (i, j) 칸 상하좌우로 0이 몇 개가 있는지 기록한다. 그리고 그 결과에 따라 빙산을 업데이트하면 된다.

void one_year_later()
{
    int zero[MAX][MAX] = {
        0,
    };
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (arr[i][j] == 0)
                continue;
            for (int dir = 0; dir < 4; dir++)
            {
                int nx = i + dx[dir];
                int ny = j + dy[dir];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && arr[nx][ny] == 0)
                    zero[i][j]++;
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            arr[i][j] = max(0, arr[i][j] - zero[i][j]);
        }
    }
    return;
}

 

bfs를 구현할 때 코드를 깔끔하게 짤 수 있는 부분이 있었다. 먼저 맨 처음에 bfs를 돌리려면 빙산이 있는 칸을 찾아야 하므로 찾는 김에 전체 빙산의 수를 센다(cnt 변수에 저장). 그리고 bfs를 돌리면서 찾은 빙산과 붙어있는 빙산의 수를 센다.(cnt2 변수에 저장) 그리고 bfs가 끝나면 visited배열을 다시 한번 돌 필요 없이 cnt, cnt2 수를 비교함으로써 빙산이 한 덩어리인지 파악할 수 있다. 

int bfs()
{
    int x, y, cnt = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (arr[i][j])
            {
                x = i;
                y = j;
                cnt++;
            }
        }
    }
    if (cnt == 0)
        return 0;

    int cnt2 = 0;
    queue<pair<int, int>> Q;

    visited[x][y] = 1;
    Q.push(make_pair(x, y));
    while (!Q.empty())
    {
        auto cur = Q.front();
        Q.pop();
        cnt2++;

        for (int dir = 0; dir < 4; dir++)
        {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];
            if (!(nx >= 0 && nx < n && ny >= 0 && ny < m))
                continue;
            if (visited[nx][ny] == 1)
                continue;
            if (arr[nx][ny] == 0)
                continue;

            visited[nx][ny] = 1;
            Q.push(make_pair(nx, ny));
        }
    }
    if (cnt == cnt2) // 빙산이 아직 한 덩어리인 경우
        return 1;
    else
        return -1;
}

또 살짝 주의할 점은, bfs를 돌리고 다시 1년 후의 빙산에 대해 bfs를 돌리기 전에 visited 배열을 초기화해줘야 한다.

/** BFS 2573 빙산 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
const int MAX = 302;
int arr[MAX][MAX];
int visited[MAX][MAX];
int n, m;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

void one_year_later()
{
    int zero[MAX][MAX] = {
        0,
    };
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (arr[i][j] == 0)
                continue;
            for (int dir = 0; dir < 4; dir++)
            {
                int nx = i + dx[dir];
                int ny = j + dy[dir];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && arr[nx][ny] == 0)
                    zero[i][j]++;
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            arr[i][j] = max(0, arr[i][j] - zero[i][j]);
        }
    }
    return;
}

int bfs()
{
    int x, y, cnt = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (arr[i][j])
            {
                x = i;
                y = j;
                cnt++;
            }
        }
    }
    if (cnt == 0)
        return 0;

    int cnt2 = 0;
    queue<pair<int, int>> Q;

    visited[x][y] = 1;
    Q.push(make_pair(x, y));
    while (!Q.empty())
    {
        auto cur = Q.front();
        Q.pop();
        cnt2++;

        for (int dir = 0; dir < 4; dir++)
        {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];
            if (!(nx >= 0 && nx < n && ny >= 0 && ny < m))
                continue;
            if (visited[nx][ny] == 1)
                continue;
            if (arr[nx][ny] == 0)
                continue;

            visited[nx][ny] = 1;
            Q.push(make_pair(nx, ny));
        }
    }
    if (cnt == cnt2) // 빙산이 아직 한 덩어리인 경우
        return 1;
    else
        return -1;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> arr[i][j];

    int res = 0;
    while (1)
    {
        res++;
        one_year_later();
        for (int i = 0; i < n; i++)
            fill(visited[i], visited[i] + m, 0);
        int flag = bfs();
        if (flag == 0)
        {
            cout << 0;
            return 0;
        }
        else if (flag == 1)
            continue;
        else
        {
            cout << res;
            return 0;
        }
    }
}