[11495번] 격자 0 만들기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 네트워크 플로우

2. 그래프 모델링

이 문제는 http://kks227.blog.me/220804885235?Redirect=Log&from=postView 링크를 참고하여 제작하였습니다.

 

격자 0 만들기 문제는 위와 같이 파란색, 빨간색으로 분리를 시켜 생각하면 편하다.

그 이유는 가로 혹은 세로의 값을 뺄때 파란색 하나와 인접한 빨간색 하나를 선택해야만 하기 때문이다.

따라서 우리는 sink와 파란색을 연결해주고 source와 빨간색을 서로 연결해준 뒤, 각 서로 인접해있는 파란색, 빨간색을 연결하는 그래프 모델링을 하고 최대 유량 알고리즘을 이용하면 우리는 원하는 결과값을 얻을 수 있다.

이때 정답은 격자값을 모두 0으로 만드는 최소 횟수 이므로 최대 유량 f + 남은 나머지 t 이다.

남은 나머지 t는 다르게 표현하면 격자값에 있는 모든 총 합을 s라 하면 s - 2*f로 표현 할 수 있다.

따라서 우리는 f + s - 2*f이므로 s - f를 정답으로 도출할 수 있다. 

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <queue>
#include <vector>
#include <algorithm>
 
#define fastio() ios::sync_with_stdio(0),cin.tie(0);
 
using namespace std;
 
const int INF = 987654321;
const int RED = 1500;
 
int arr[55][55];
pair<int, int> map[55][55];
 
vector<int> adj[3011];
int c[3011][3011];
int f[3011][3011];
 
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,-1,0,1 };
 
int S = 0, T = 3003;
 
int main()
{
    fastio();
 
    int tc;
    cin >> tc;
 
    while (tc--)
    {
        int n, m;
        cin >> n >> m;
 
        memset(arr, 0, sizeof(arr));
        memset(c, 0, sizeof(c));
        memset(f, 0, sizeof(f));
        memset(map, 0, sizeof(map));
 
        for (int i = 0; i < 3011; i++)
            adj[i].clear();
 
        vector<int> blue, red;
 
        int total = 0;
        bool chk = true; // blue일때 true
        int r = 1, b = 1;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                cin >> arr[i][j];
 
                total += arr[i][j];
 
                if (chk)
                {
                    blue.push_back(arr[i][j]);
                    map[i][j] = { 1, b++ };
                }
                else
                {
                    red.push_back(arr[i][j]);
                    map[i][j] = { -1, r++ };
                }
                chk = !chk;
            }
            if (m % 2 == 0)
                chk = !chk;
        }
 
        r = 1 + RED, b = 1;
 
        for (int i = 0; i < blue.size(); i++)
        {
            c[S][b] = blue[i];
 
            adj[S].push_back(b);
            adj[b].push_back(S);
 
            b++;
        }
 
        for (int i = 0; i < red.size(); i++)
        {
            c[r][T] = red[i];
 
            adj[r].push_back(T);
            adj[T].push_back(r);
 
            r++;
        }
 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (map[i][j].first == 1)
                {
                    for (int k = 0; k < 4; k++)
                    {
                        int ni = i + dy[k];
                        int nj = j + dx[k];
 
                        if (!(0 <= ni && ni < n) || !(0 <= nj && nj < m))
                            continue;
 
                        int b = map[i][j].second;
                        int r = map[ni][nj].second + RED;
                        c[b][r] = INF;
 
                        adj[b].push_back(r);
                        adj[r].push_back(b);
                    }
                }
 
            }
 
        }
 
        int totalFlow = 0;
 
        while (1)
        {
            vector<int> prev(3004, -1);
 
            queue<int> q;
            q.push(S);
 
            while (!q.empty() && prev[T] == -1)
            {
                int here = q.front();
                q.pop();
 
                for (int i = 0; i < adj[here].size(); i++)
                {
                    int next = adj[here][i];
                    if (prev[next] != -1)
                        continue;
 
                    if (c[here][next] - f[here][next] > 0)
                    {
                        q.push(next);
                        prev[next] = here;
                    }
                }
            }
            if (prev[T] == -1)
                break;
 
            int flow = INF;
 
            for (int i = T; i != S; i = prev[i])
                flow = min(flow, c[prev[i]][i] - f[prev[i]][i]);
 
            for (int i = T; i != S; i = prev[i])
            {
                f[prev[i]][i] += flow;
                f[i][prev[i]] -= flow;
            }
            totalFlow += flow;
 
        }
 
        cout << total - totalFlow << endl;
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>