[BOJ 11495] 격자 0 만들기

문제

---

https://www.acmicpc.net/problem/11495

풀이

---

격자를 체스판처럼 생각해 두 부분으로 나눈다.

즉 행과 열의 홀짝이 같은 칸들과 다른 칸들로 나눈다.

인접한 정수 2개를 고르는 것은 이 두 부분에서 하나씩 고르는 것이므로 한 부분에서 다른 부분으로 흐르는 flow network를 생각할 수 있다.

source에서 한 부분으로 가는 엣지의 capacity를 각 칸의 정수로 놓고, 다른 부분에서 sink로 가는 엣지의 capacity 또한 각 칸의 정수로 놓는다.

한 부분에서 다른 부분으로 가는 엣지들의 capacity는 충분히 크기만 하면 된다.

그러면 최대 flow는, 최소 연산으로 모든 정수를 0으로 만드는 과정에서, 어느 인접한 두 정수도 모두 양수이지 않을 때까지의 연산 횟수이다.

다시 말하자면, 최대 flow만큼 연산을 적용시킨 후엔 한 칸씩 1 감소시켜야 한다.

그래서 격자 위 남은 모든 양수들의 합만큼 연산을 더 해주면 된다.

정답의 최소성이 보장되는 이유는 flow network의 성질에서 기인한다.

코드

---

#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

typedef pair<int, int> pii;
int n, m, ans;
int board[50][50], graph[2502][2502];

void init() {
    memset(graph, 0, sizeof(graph));

    cin >> n >> m;
    ans = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int temp;
            cin >> temp;
            board[i][j] = temp;
            ans += temp;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if ((i + j) % 2 == 0) {
                graph[0][m * i + j + 1] = board[i][j];
                if (i > 0) graph[m * i + j + 1][m * (i - 1) + j + 1] = max(board[i][j], board[i - 1][j]);
                if (i < n - 1) graph[m * i + j + 1][m * (i + 1) + j + 1] = max(board[i][j], board[i + 1][j]);
                if (j > 0) graph[m * i + j + 1][m * i + j] = max(board[i][j], board[i][j - 1]);
                if (j < m - 1) graph[m * i + j + 1][m * i + j + 2] = max(board[i][j], board[i][j + 1]);
            }
            else graph[m * i + j + 1][n * m + 1] = board[i][j];
        }
    }
}

void solve() {
    while (true) {
        int res, prev[n * m + 2];
        fill_n(prev, n * m + 2, -1);
        queue<pii> Q;
        Q.push(pii(0, 1000));

        while (Q.size()) {
            pii edge = Q.front();
            int cur = edge.first;
            res = edge.second;
            Q.pop();

            if (!cur) {
                for (int x = 0; x < n; x++) {
                    for (int y = x % 2; y < m; y += 2) {
                        int nxt = m * x + y + 1;
                        if (prev[nxt] == -1 && graph[cur][nxt]) {
                            prev[nxt] = cur;
                            Q.push(pii(nxt, min(res, graph[cur][nxt])));
                        }
                    }
                }
            }
            else {
                if (graph[cur][n * m + 1]) {
                    res = min(res, graph[cur][n * m + 1]);
                    prev[n * m + 1] = cur;
                    break;
                }
                int i = (cur - 1) / m;
                int j = (cur - 1) % m;

                vector<int> adj;
                if (i > 0) adj.push_back(m * (i - 1) + j + 1);
                if (i < n - 1) adj.push_back(m * (i + 1) + j + 1);
                if (j > 0) adj.push_back(m * i + j);
                if (j < m - 1) adj.push_back(m * i + j + 2);

                for (int nxt : adj) {
                    if (prev[nxt] == -1 && graph[cur][nxt]) {
                        prev[nxt] = cur;
                        Q.push(pii(nxt, min(res, graph[cur][nxt])));
                    }
                }
            }
            if (prev[n * m + 1] != -1) break;
        }
        if (prev[n * m + 1] == -1) break;

        ans -= res;
        int nxt = n * m + 1;
        while (nxt) {
            int cur = prev[nxt];
            graph[cur][nxt] -= res;
            graph[nxt][cur] += res;
            nxt = cur;
        }
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(NULL); cin.tie(NULL);
    ios::sync_with_stdio(false);

    int t;
    cin >> t;
    while (t--) {
        init();
        solve();
    }
}

파이썬으로 TLE를 뚫을 수 있을지 모르겠다.

파이썬으로 AC를 받은 사람들도 존재하나, 아직은 모르는 디닉 알고리즘 (Dinic’s Algorithm)이 더 빠르다고 한다.

그래서 C++로 짜봤다.

여전히 TLE가 떴던 건 최적화가 부족해서였다.

bfs 과정에서 연결된 엣지들만을 대상으로 탐색해야 했다.

WA를 받았던 건, graph 배열을 초기화하지 않아서였다.

C++은 파이썬보다 선언, 초기화 이런 것들이 더욱 중요한 것 같다.