글 읽기 - 비숍 2) 이분 매칭 관련 문제

nuclear852 4년 전 0

이분 매칭 관련 문제입니다.

룩 문제처럼 맵을 왼쪽위 대각선으로 올라가는 방향, 그리고 오른쪽 위 대각선으로 올라가는 방향 따로 해서

gmap과 smap을 만들었는데요, 규칙에 따라 비숍이 놔줄 수 있는 번호들을 mapping 했습니다.

이후 A 그룹을 gmap, B 그룹을 smap이라 두고

gmap과 smap끼리 매칭되는 번호들을 adj[gmap[i][j]]에 smap[i][j]를 넣어주는 방식으로 묶습니다.

이후 hopcroft-karp algorithm을 이용하여 최대 매칭을 찾아주는 방식으로 하여 정답을 찾았는데요,

테스트케이스에서는 맞는 것 같으나, 바로 틀렸습니다가 나옵니다.

해당하는 알고리즘이 어떤 문제점이 있는지 알려주시면 감사하겠습니다.

#include <stdio.h>
#include <queue>
#include <vector>

using namespace std;

int N;
bool map[103][103];
int gmap[103][103];
int smap[103][103];

int garo = 1;
int sero = 1;

int A[10004], B[10004], lv[10004];
bool pos[10004];

vector<int> adj[10004];

void bfs(){
	queue<int> q;
	for(int i=1; i<=garo; i++){
		if(A[i] == -1){
			lv[i] = 0;
			q.push(i);
		}
		else{
			lv[i] = -5;
		}
	}
	while(!q.empty()){
		int idx = q.front(); q.pop();
		for(auto x : adj[idx]){
			if(B[x] != -1 && lv[B[x]] == -5){
				lv[B[x]] = lv[idx] + 1;
				q.push(x);
			}
		}
	}
}

bool dfs(int n){
	if(!pos[n]) return pos[n];
	
	for(auto x : adj[n]){
		if(B[x] == -1 || (lv[B[x]] == lv[n] + 1 && dfs(B[x]))) {
			A[n] = x;
			B[x] = n;
			return 1;
		}
	}
	
	return pos[n] = 0;
}

int main(){
	scanf("%d", &N);
	int temp; scanf("%d", &temp);
	
	for(int i=0; i<temp; i++){
		int x,y; scanf("%d%d", &x, &y);
		map[x][y] = 1;
	}
	
	int x = N, y = 1;
	
	for(int i=1; i<10004; i++){
		A[i] = -1;
		B[i] = -1;
	}
	
	while(1)
	{
		if(!map[x][y]){
			gmap[x][y] = garo;
			x--; y--;
		}
		else {
			garo++;
			x--; y--;
		}
		if(x == 0 && y == N-1) break;
		if(x == 0 && y == 0){
			x = N-1; y = N;
			garo++;
		}
		if(y == 0) {
			y = N - x + 1;
			x = N;
			garo++;
		}
		if(x == 0) {
			x = N - y - 1;
			y = N;
			garo++;
		}
	}
	
	x = N; y = N;
	while(1)
	{
		if(!map[x][y]){
			smap[x][y] = sero;
			x--; y++;
		}
		else {
			sero++;
			x--; y++;
		}
		if(x == 0 && y == 2) break;
		if(x == 0 && y == N+1){
			x = N-1; y = 1; sero++;
		}
		if(y == N+1){
			y = x; x = N;
			sero++;
		}
		if(x == 0) {
			x = y - 2; y = 1;
			sero++;
		}
	}
	
	for(int i=1; i<=N; i++){
		for(int j=1; j<=N; j++){
			if(!map[i][j]) {
				adj[ gmap[i][j] ].push_back(smap[i][j]);
			}
		}
	}
	
	int ans = 0;
	while(1) {
		bfs();
		for(int i=1; i<=garo; i++) pos[i] = 1;
		int flow = 0;
		for(int i=1; i<=garo; i++){
			if(A[i] == -1 && dfs(i)) flow++;
		}
		if(!flow) break;
		ans += flow;
	}
	
	printf("%d", ans);
	
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

비숍 2) 이분 매칭 관련 문제

nuclear852 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말