boj, 백준) 11495. 격자 0 만들기 ( C / C++ )

1. 문제 링크

www.acmicpc.net/problem/11495

11495번: 격자 0 만들기

 

2. 문제 개요

음수가 아닌 정수들의 격자가 주어진다. 

- 격자에서 가로 또는 세로로 인접한 정수 2개를 고른다.

- 각 정수가 양수일 때 1 감소시킨다.

 

격자가 주어졌을 때 모든 정수를 0으로 만들기 위해 필요한 최소 연산의 횟수를 구하는 프로그램을 작성하시오.

 

3. 문제 힌트

우선, [0, 1] 을 선택했을 때, [-1, 0]이 되는 게 아닌가.. 생각했는데, 문제가 조금 이상한가 제가 잘못 이해했는가는 잘 모르겠습니다. [0, 1]을 선택하면 [0, 0]이 된다고 생각하고 풀었습니다.

 

격자를 체스판처럼 흑과 백으로 구분지어 생각해 봅시다.

그리고 이웃한 다른색의 칸과 연결시켜줍시다.

이 '연결'이란 한번 묶는다는 의미로 최대 유량은 묶는 횟수를 의미합니다.

그리고 묶어서 처리할 수 없는 숫자, 즉, 이웃한 칸이 모두 0인 경우는 모두 그냥 더해줍시다. (블록 1개만 처리한다고 생각)

 

 

4. 문제 풀이

 위와 같이 분리를 해줍시다.

 

문제에서 이웃한 두개의 칸을 묶어 1씩 감소한다고 했기 때문에 간선을 이웃한 다른 색깔의 칸만 연결시켜줍시다.

예를 들면, 흰색 5번같은 경우는 2, 4, 6, 8과 용량이 무한대인 간선을 갖게 됩니다.

 

그림판이라..

위처럼 모델링을 해줍시다.

source -> 흰색칸, 검은칸 -> sink  간의 용량은 격자의 정수 값으로 할당해 줍시다.

그리고 흰색칸 <-> 검은칸 간 간선의 용량은 무한대로 설정해 줍시다. 각 격자의 최댓값이 정해져 있어서 최댓값으로 하면 되는데 그냥 무한대로 해줬습니다.

 

여기서의 최대유량의 의미는 2개를 묶어서 처리할 수 있는 최소 횟수입니다.

그러면 2개를 묶어서 처리할 수 없는 상황이 나오는데, 그럴 때는 1개만 처리를 해줘야 합니다.

최대 유량은 2개를 묶어서 처리할 수 있는 모든 경우를 다 처리해줬기 때문에 최대 유량을 구한 뒤의 격자는 모두 다 혼자만 처리해야 하는 격자들입니다.

 

그래서 사전에 값을 입력받을 때, 모든 격자의 정수의 합을 구한 뒤에 최대 유량의 x2만큼 빼주어 현재 남아있는 횟수를 구할 수 있습니다.

 

최대 유량을 통해 구한 값은 2개를 묶어 처리했기 때문에 최대 유량 x 2는 격자에서 뺀 숫자의 합입니다.

 

 

에드몬드 카프 알고리즘을 사용했습니다.

더 빠른 알고리즘을 사용하면 50~70ms에도 풀 수 있습니다.

 

5. 코드

#include <cstdio>
#include <vector>
#include <string.h>
#include <queue>
using namespace std;

int const src = 2500, sink = 2501, INF = 987654321;
int t, ans, sum;
const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,1,-1 };
int value[50][50];
int capacity[2502][2502], flow[2502][2502];
vector<int> adj[2502];
queue<int> q;

void edmond_karp()
{
	int p[2502];

	while (1)
	{
		memset(p, -1, sizeof(p));
		q.push(src);
		p[src] = -2;
		

		while (!q.empty()) {
			int cur = q.front(); q.pop();

			for (int next : adj[cur]){

				if (p[next] == -1 && capacity[cur][next] - flow[cur][next] > 0) {

					//flow
					p[next] = cur;
					q.push(next);

					if (next == sink)			
						break;
					
				}
			}
		}
		if (p[sink] == -1)
			break;

		int minflow = INF;

		for (int idx = sink; idx != src; idx = p[idx])
			minflow = min(minflow, capacity[p[idx]][idx] - flow[p[idx]][idx]);

		for (int idx = sink; idx != src; idx = p[idx]) {
			flow[p[idx]][idx] += minflow;
			flow[idx][p[idx]] -= minflow;
		}
		ans += minflow;

	}

	ans += sum - (ans * 2);
	return;
}

int main()
{
	scanf("%d", &t);

	while (t--)
	{
		int n, m;
		scanf("%d %d", &n, &m);

		//initialize
		memset(value, 0, sizeof(value));
		memset(capacity, 0, sizeof(capacity));
		memset(flow, 0, sizeof(flow));
		for (int i = 0; i < 2502; ++i)
			adj[i].clear();
		ans  = sum = 0;
		q = queue<int>();

		for (int i = 0; i < n; ++i)
			for (int j = 0; j < m; ++j) {
				scanf("%d", &value[i][j]);
				sum += value[i][j];
				if ((i + j) % 2 == 0) {
					adj[src].push_back(i*m + j);
					adj[i*m + j].push_back(src);

					capacity[src][i*m + j] = value[i][j];
					
				}
				else {
					adj[i*m + j].push_back(sink);
					adj[sink].push_back(i*m + j);

					capacity[i*m + j][sink] = value[i][j];
				}
			}

		for (int cy = 0; cy < n; ++cy) 
			for (int cx = 0; cx < m; ++cx) 
				if ((cy + cx) % 2 == 0)
					for (int dir = 0; dir < 4; ++dir) {

						int nx = cx + dx[dir];
						int ny = cy + dy[dir];

						if (nx < 0 || ny < 0 || nx >= m || ny >= n)
							continue;
					 
							adj[cy*m + cx].push_back(ny*m + nx);
							adj[ny*m + nx].push_back(cy*m + cx);
							capacity[cy*m + cx][ny*m + nx] = INF;
					}
			
		

		edmond_karp();
		

		printf("%d\n", ans);
		
	}

	return 0;
}

 

6. 결과