글 읽기 - bfs 구현에서의 문제점

nick1324 4년 전 0

축사장 이 문제를 dfs로 구현했다가 bfs로 바꾸고 있는데 어디가 잘못 된건지 모르겠네요 ㅠㅠ 혹시 도와주실 수 있나요 bfs 구현할 때 어디가 잘못된걸 까요?... 제가 디버깅 해보면 예제에 있는 걸 입력하면 4번 째 까지 잘 되다가 5번 째에서 틀어지는데 어떻게 해결해야될 지 모르겠네요 도와주세요 ㅠ

#include <cstdio>
#include <vector>
#include <algorithm>
#include<queue>
using namespace std;
const int MAX = 200;
queue<int> q;
// N: A 그룹 크기, M: B 그룹 크기
// A[i], B[i]: 각 정점이 매칭된 반대편 정점 번호
int N, M, A[MAX], B[MAX];
// adj[i]: A[i]와 인접한 그룹 B의 정점들
vector<int> adj[MAX];
bool visited[MAX];

// A그룹에 속한 정점 a를 이분 매칭시켜서 성공하면 true
bool dfs(int a) {//a가 소라고 생각하기 즉 몇 번째 소인지
	visited[a] = true;//a가 왼쪽 정점 b가 오른쪽 정점이라고 생각하기!!!!! 중요 a번 째 정점 b번 째 정점 이렇게
	for (int b : adj[a]) {
		// 반대편이 매칭되지 않았거나
		// 매칭되어 있었지만 원래 매칭되어 있던 정점을 다른 정점과 매칭시킬 수 있으면 성공
		if (B[b] == -1 || (!visited[B[b]] && dfs(B[b]))) {//여기 visited는 
			A[a] = b;//오른쪽 정점에 저장되어 있는 왼쪽 정점에 정보가 있으면 참이다
			B[b] = a;//즉 참일 시 저장되어 있는 왼쪽 정점이 다른 오른쪽 정점으로 옮겨야되는 것
			return true;//그래서 그 B[b]를 인자로 dfs로 다른 점으로 옮기려고 호출하는 것
		}
	} 
	// 매칭 실패
	return false;
}
bool bfs(int a)
{
	q.push(a);
	visited[a] = true;
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		//printf("%d ", x);
		for (int b : adj[x])
		{
			if (B[b]==-1 || (!visited[B[b]]&&bfs(B[b])))
			{
				A[x] = b;
				B[b] = x;
				return true;
			}
		}
	}
}
int main()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		int S;
		scanf("%d", &S);
		for (int j = 0; j < S; j++) {
			int k;
			scanf("%d", &k);
			adj[i].push_back(k - 1);
		}
	}

	int match = 0;
	// 초기값: -1
	fill(A, A + N, -1);//memset 과 비슷한 함수 A부터 A+N까지의 원소를 -1로 만듬
	fill(B, B + M, -1);
	for (int i = 0; i < N; i++) {
		// 아직 매칭되지 않은 그룹 A 정점에 대해 매칭 시도
		if (A[i] == -1) {
			// visited 배열 초기화
			fill(visited, visited + N, false);
			//if (dfs(i)) 
		  if(bfs(i))
				match++;
		}
	}
	printf("%d\n", match);
}

chogahui05 4년 전 0

이분 매칭은 어떻게 동작하는 알고리즘인가요?

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

문제

문제

출처

ICPC

bfs 구현에서의 문제점

nick1324 4년 전 0

chogahui05 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말