boj, 백준 ) 10937. 두부 모판 자르기 ( C / C++)

1. 문제 링크

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

10937번: 두부 모판 자르기

2. 문제 개요

 두부를 (1x2) 혹은 (2x1)로 잘라서 상품가치가 가장 높은 가격을 구하는 프로그램 구하기.

 

3. 문제 힌트

   격자무늬 ( 체스판) 모양으로 그룹핑을 해서 이분 그래프로 나타낸다.

(1x2) , (2x1)이므로 인접한 칸과 매핑한다. 그 후 MCMF 알고리즘을 사용하여 최대 매칭의 최대 비용(음수)을 구하는데 조건이 있다.

 

최대 매칭이 꼭 정답이라는 보장이 없다.

 

4. 문제 풀기

격자무늬로 모델링하고 mcmf를 구현한다.

 

그런데 다음과 같은 경우 틀린 답을 출력한다.

4

CAAC

AAAA

AAAA

AAAA

이다.

 

'최대 매칭'을 할 경우 680인 값을 내놓는다 왜냐하면 1행의 CAAC가 AA가 매칭되었다가 CA AC로 분리가 된다. (최대 매칭을 하기 때문)

따라서 매칭을 1번 할때마다 전체 비용이 감소한다면 mcmf를 그만두고 바로 값을 반환해야 한다.

최대 비용이기 때문에 코드에서는 비용을 음수로 두었고 절댓값이 커지는 경우에 mcmf를 탈출하도록 했다.

 

5. 코드

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;

vector<string> v;
//black 1~125, white 126~250,,, src=251, sink=252
const int white = 125, max_size = 253, src = 251, sink = 252, INF = 987654321;
const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,1,-1 };

int cost[max_size][max_size], c[max_size][max_size], f[max_size][max_size];
int numbering[max_size][max_size];
int wnum = 0, bnum = 0;

int mcmf()
{
	int ans = 0;
	int new_ans = 0;

	while (1)
	{
		int p[max_size], d[max_size];
		fill(p, p + max_size, -1);
		fill(d, d + max_size, INF);

		bool inq[max_size] = { false, };
		queue<int> q;

		q.push(src);
		inq[src] = true;
		d[src] = 0;
		p[src] = src;

		while (!q.empty())
		{
			int cur = q.front(); q.pop();
			inq[cur] = false;

			for (int next = 0; next < max_size; ++next)
			{
				if (c[cur][next] - f[cur][next] > 0 && d[next] > d[cur] + cost[cur][next])
				{
					d[next] = d[cur] + cost[cur][next];
					p[next] = cur;
					if (!inq[next])
					{
						q.push(next);
						inq[next] = true;
					}
				}
			}
		}
		if (p[sink] == -1)
			break;

		int minflow = INF;
		for (int i = sink; i != src; i = p[i])
			minflow = min(minflow, c[p[i]][i] - f[p[i]][i]);

		for (int i = sink; i != src; i = p[i])
		{
			new_ans += minflow*cost[p[i]][i];

			f[p[i]][i] += minflow;
			f[i][p[i]] -= minflow;
		}

		if (new_ans <= ans)
			ans = new_ans;
		else
			break;
	}

	return -ans;
}


int cal_cost(char a, char b)
{
	if (a == 'A' && b == 'A')
		return 100;

	if ((a == 'A' && b == 'B') || (a == 'B' && b == 'A'))
		return 70;

	if ((a == 'A' && b == 'C') || (a == 'C' && b == 'A'))
		return 40;

	if (a == 'B' && b == 'B')
		return 50;

	if ((a == 'B' && b == 'C') || (a == 'C' && b == 'B'))
		return 30;

	if (a == 'C' && b == 'C')
		return 20;

	return 0;
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	v.resize(n);

	for (int i = 0; i < n; ++i)
		cin >> v[i];

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			//black
			if ((i + j) % 2 == 0)
				numbering[i][j] = bnum++;
			else
				numbering[i][j] = white + wnum++;
		}
	}

	//matching
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if ((i + j) % 2 == 0) {
				for (int dir = 0; dir < 4; ++dir) {
					int ny = i + dy[dir];
					int nx = j + dx[dir];
					if (nx < 0 || ny < 0 || nx >= n || ny >= n)
						continue;
					c[numbering[i][j]][numbering[ny][nx]] = 1;
					cost[numbering[i][j]][numbering[ny][nx]] = -1 * cal_cost(v[i][j], v[ny][nx]);
					cost[numbering[ny][nx]][numbering[i][j]] = cal_cost(v[i][j], v[ny][nx]);
				}
			}
		}
	}

	//src black
	for (int i = 0; i < bnum; ++i)
		c[src][i] = 1;

	//white -> sink
	for (int i = white; i < white + wnum; ++i)
		c[i][sink] = 1;

	printf("%d", mcmf());
	return 0;
}

6. 결과 사진

지적, 댓글 언제나 환영입니다~