취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1536번 문제인 Dance, Dance이다.
문제는 아래 링크를 확인하자.

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

남자 N명과 여자 N명이 각자 최대 K명까지 "서로 좋아하지 않는" 사람과 춤을 출 수 있고, 한번 춤췄던 쌍은 다시 춤을 추지 못할 때 춤을 최대 몇 번 출 수 있는가를 구하는 문제이다.

춤을 M번 출 수 있는지 판단하는 결정문제를 해결할 수 있다면, 이분탐색을 통해 답을 구해낼 수 있을 것이다. 따라서, M이 주어졌을 때 춤을 M번 출 수 있을지를 판단하는 방법을 살펴보자.

각 남자와 여자는 서로 좋아하는 사람과는 춤을 추는 데에 제한이 없지만 그렇지 않은 경우는 각자 K번 이하가 되어야 한다. 그러므로 제한없이 춤을 출 수 있는 횟수와 제한에 포함되는 횟수를 분리하여 아래와 같은 구조의 네트워크 그래프를 만들어 max flow가 M*N과 일치하는지를 살피는 것으로 문제를 해결할 수 있다.

source --<가중치: M>-- 각 남자 노드 --<가중치: INF(서로 좋아하는 쌍), K(그렇지 않은 쌍)>-- 각 남자의 좋아하는/그렇지 않은 사람과 춤추는 것을 체크하기 위한 노드 --<가중치: 1>-- 각 여자의 좋아하는/그렇지 않은 사람과 춤추는 것을 체크하기 위한 노드  --<가중치: INF(서로 좋아하는 쌍), K(그렇지 않은 쌍)>-- 각 여자 노드 --<가중치: M>-- sink

글쓴이는 dinic 알고리즘을 이용하여 문제를 해결하였다.

아래의 구현에서 각 노드의 인덱스는 다음과 같은 의미이다:

0: source

0*N+k+1: k번 남자 노드

1*N+k+1: k번 남자가 좋아하는 사람과 춤추는 것을 체크하기 위한 노드

2*N+k+1: k번 남자가 좋아하지 않은 사람과 춤추는 것을 체크하기 위한 노드

3*N+k+1: k번 여자 노드

4*N+k+1: k번 여자가 좋아하는 사람과 춤추는 것을 체크하기 위한 노드

5*N+k+1: k번 여자가 좋아하지 않은 사람과 춤추는 것을 체크하기 위한 노드

6*N+1: sink

아래는 제출한 소스코드이다.

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

int N, K;
string board[50];
vector<int> G[302];
int edge[302][302];

int level[302];
bool bfs() {
	memset(level, 0, sizeof(level));
	level[0] = 1;
	queue<int> que;
	que.push(0);
	while (!que.empty()) {
		int current = que.front(); que.pop();
		for (auto node : G[current]) {
			if (level[node]) continue;
			if (edge[current][node]) {
				level[node] = level[current] + 1;
				que.push(node);
			}
		}
	}

	return level[6 * N + 1];
}

int turn[302];
int dfs(int current, int flow) {
	if (current == 6 * N + 1) return flow;
	int cursize = G[current].size();
	for (int& i = turn[current]; i < cursize; i++) {
		int node = G[current][i];
		if (edge[current][node] && level[node] == level[current] + 1) {
			int f = dfs(node, min(edge[current][node], flow));
			if (f) {
				edge[current][node] -= f;
				edge[node][current] += f;
				return f;
			}
		}
	}
	return 0;
}

bool func (int X) {
	memset(edge, 0, sizeof(edge));
	for (int r = 0; r < N; r++) {
		edge[0][r + 1] = X;
		edge[r + 1][N + r + 1] = 1000000007;
		edge[r + 1][2 * N + r + 1] = K;
		edge[3 * N + r + 1][6 * N + 1] = X;
		edge[4 * N + r + 1][3 * N + r + 1] = 1000000007;
		edge[5 * N + r + 1][3 * N + r + 1] = K;
		for (int c = 0; c < N; c++) {
			if (board[r][c] == '1') edge[N + r + 1][4 * N + c + 1] = 1;
			else edge[2 * N + r + 1][5 * N + c + 1] = 1;
		}
	}

	int flow = 0;

	while (bfs()) {
		memset(turn, 0, sizeof(turn));
		int f;
		while (f = dfs(0, 1000000007)) flow += f;
	}

	return flow == N * X;
}

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

	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> board[i];
	for (int r = 0; r < N; r++) {
		G[0].emplace_back(r + 1);
		G[r + 1].emplace_back(0);
		G[r + 1].emplace_back(N + r + 1);
		G[N + r + 1].emplace_back(r + 1);
		G[r + 1].emplace_back(2 * N + r + 1);
		G[2 * N + r + 1].emplace_back(r + 1);
		G[6 * N + 1].emplace_back(3 * N + r + 1);
		G[3 * N + r + 1].emplace_back(6 * N + 1);
		G[3 * N + r + 1].emplace_back(4 * N + r + 1);
		G[4 * N + r + 1].emplace_back(3 * N + r + 1);
		G[3 * N + r + 1].emplace_back(5 * N + r + 1);
		G[5 * N + r + 1].emplace_back(3 * N + r + 1);
		for (int c = 0; c < N; c++) {
			if (board[r][c] == '1') {
				G[N + r + 1].emplace_back(4 * N + c + 1);
				G[4 * N + c + 1].emplace_back(N + r + 1);
			}
			else {
				G[2 * N + r + 1].emplace_back(5 * N + c + 1);
				G[5 * N + c + 1].emplace_back(2 * N + r + 1);
			}
		}
	}

	int L = 0, R = 50;
	while (L < R) {
		int mid = (L + R) / 2 + 1;
		if (func(mid)) L = mid;
		else R = mid - 1;
	}

	cout << L;
}