2573 빙산

문제 링크

• 내 풀이

#define _CRT_SECURE_NO_WARNINGS

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

#define pii pair<int,int>

using namespace std;

constexpr int dr[4] = { -1, 1, 0, 0 }, dc[4] = { 0, 0, -1, 1 };

struct dt {
    int r, c, v;
};

int N, M, m[300][300], ck[300][300];
queue<pii> q;

int cntShore(int r, int c)
{
    int ret = 0;
    for (int d = 0; d < 4; d++)
    {
        int nr = r + dr[d];
        int nc = c + dc[d];

        if (!m[nr][nc])
        {
            ret += 1;
        }
    }

    return ret;
}

int solve()
{
    vector<dt> dtlst;

    int a = 1, ret = 0;
    while (a)
    {
        for (int r = 0; r < N; r++) for (int c = 0; c < M; c++)
            ck[r][c] = 0;

        a = 0;
        for (int r = 1; r < N - 1; r++)
        {
            for (int c = 1; c < M - 1; c++)
            {
                if (!m[r][c] || ck[r][c])
                    continue;

                if (m[r][c] && ck[r][c] == 0 && a)
                    return ret;

                q.push({ r, c });
                ck[r][c] = 1;
                a = 1;

                while (!q.empty())
                {
                    int rr = q.front().first;
                    int cc = q.front().second;

                    dtlst.push_back({ rr, cc, cntShore(rr, cc) });

                    for (int d = 0; d < 4; d++)
                    {
                        int nr = rr + dr[d];
                        int nc = cc + dc[d];

                        if (!m[nr][nc] || ck[nr][nc])
                            continue;
                        q.push({ nr, nc });
                        ck[nr][nc] = 1;

                    }

                    q.pop();
                }

                for (const auto& dt : dtlst)
                {
                    m[dt.r][dt.c] -= dt.v;
                    if (m[dt.r][dt.c] < 0)
                        m[dt.r][dt.c] = 0;
                }

                dtlst.clear();
            }
        }
        ret += 1;
    }

    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;

    for (int r = 0; r < N; r++)
    {
        for (int c = 0; c < M; c++)
        {
            cin >> m[r][c];
        }
    }

    int result = solve();
    cout << result << "\n";
    return 0;
}

빙산의 위치를 찾기 위해 전체를 매번 스캔하여 오버헤드가 발생하였다.

• 다른 사람 풀이

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

struct Point {
    int x, y;
};

queue<Point> q;
vector<Point> v;
bool visited[310][310] = { 0, };
int graph[310][310] = { 0, };
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { 1, 0, -1, 0 };
int n, m, year = 0, totalGlacier = 0;

int main(void) {
    scanf("%d %d", &n, &m);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &graph[i][j]);
            if (graph[i][j] != 0) v.push_back({ j , i });
        }
    }

    totalGlacier = v.size();

    while (true) {
        // Search a first node for bfs
        for (int i = 0; i < v.size(); i++) {
            if (graph[v[i].y][v[i].x] > 0) {
                q.push(v[i]); visited[v[i].y][v[i].x] = true;
                break;
            }
        }

        // Start bfs
        int cnt = 0, numOfMeltedIce = 0;
        while (!q.empty()) {
            Point cur = q.front(); q.pop();
            int numOfWater = 0;
            cnt++;

            for (int i = 0; i < 4; i++) {
                Point next = { cur.x + dx[i], cur.y + dy[i] };

                if (!visited[next.y][next.x] && graph[next.y][next.x] <= 0) numOfWater++;
                if (!visited[next.y][next.x] && graph[next.y][next.x] > 0) {
                    q.push({ next.x, next.y });
                    visited[next.y][next.x] = true;
                }
            }
            graph[cur.y][cur.x] -= numOfWater;

            if (graph[cur.y][cur.x] <= 0) numOfMeltedIce++;
        }
        memset(visited, 0, sizeof(visited));
        year++;

        if (cnt != totalGlacier) {
            printf("%d", year - 1);
            return 0;
        }

        totalGlacier -= numOfMeltedIce;

        if (totalGlacier == 0) {
            printf("0");
            return 0;
        }
    }
}

먼저 빙상의 위치와 갯수를 미리 저장하여 오버헤드를 줄였다. 본받아야 겠다.