취미로 코딩하기

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

이번에 볼 문제는 백준 5398번 문제인 틀렸습니다이다.
문제는 아래 링크를 확인하자.

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

모든 가로단어끼리와 세로단어끼리는 겹치지 않는다고 조건에 주어져있으므로, 각 가로단어와 세로단어를 노드로 생각하고 퍼즐 위에서 겹치는 칸의 글자가 서로 다른 두 단어끼리 간선을 이어주면 이분그래프(bipartite graph)를 하나 만들 수 있다. 이 그래프에서 최대한 많은 단어를 적어넣을 때의 경우의 수를 구하는 것은 위에서 구한 이분그래프에서 노드의 최대 독립 집합(maximum independent set)의 크기를 찾는 문제로 볼 수 있고, 이분그래프에서 이는 maximum bipartite matching의 수를 이용하여 간단히 계산할 수 있다.

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

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

int board[2001][2001][2];

vector<int> G[501];
int visited[501];
int matching[501];

int bipartite(int current) {
	if (visited[current]) return 0;
	visited[current] = 1;
	for (auto node : G[current]) {
		if (matching[node] == 0) {
			matching[node] = current;
			return 1;
		}
		if (bipartite(matching[node])) {
			matching[node] = current;
			return 1;
		}
	}
	return 0;
}

void solve() {
	for (int i = 1; i <= 500; i++) G[i].clear();
	memset(matching, 0, sizeof(matching));
	memset(board, 0, sizeof(board));

	int garo, sero; cin >> garo >> sero;
	for (int i = 1; i <= garo; i++) {
		int x, y; string s; cin >> x >> y >> s;
		int slen = s.length();
		for (int k = 0; k < slen; k++) {
			board[y][x + k][0] = s[k], board[y][x + k][1] = i;
		}
	}
	for (int i = 1; i <= sero; i++) {
		int x, y; string s; cin >> x >> y >> s;
		int slen = s.length();
		for (int k = 0; k < slen; k++) {
			if (board[y + k][x][0] != s[k]) {
				G[board[y + k][x][1]].push_back(i);
			}
		}
	}

	int ans = 0;
	for (int i = 1; i <= garo; i++) {
		memset(visited, 0, sizeof(visited));
		ans += bipartite(i);
	}

	cout << garo + sero - ans << '\n';
}

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

	int T; cin >> T;
	while (T--) {
		solve();
	}
}