[백준BOJ] 2188 축사 배정

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

2188번: 축사 배정

---

문제해설

N의 입력 범위가 작기 때문에, 소를 계속 가능한 위치에 이동시켜주면서 풀어 나가면 됩니다.

또한, 네트워크 플로우의 특성인 어느 소부터 시작하던지, 결국 되는경우는 모두 처리가 되기 때문에,

1번 소부터 N번 소까지 차레대로 처리해주면 됩니다.

k번 소를 원하는 지역에 넣으려고 하는 경우 두가지 케이스가 있습니다

case 1 ) 해당 지역이 비어있는 경우

case 2 ) 다른소가 차지하고 있는 경우

 

< case 1 >

해당 지역에 k번째 소를 넣어주고

k번째 소가 어느위치에 있는지도 알고 있어야 합니다.

 

< case 2 >

해당 지역에 있는 소를 y소라고 한다면,

y소를 다른위치로 옮겨야 합니다.

재귀 함수를 사용해서, y소를 다른 지역에 옮길 수 있는지 확인한뒤

(옮긴 후) k번째 소를 해당 지역에 넣어 주면 됩니다.

 

---

전체코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
//--------------------------------------------------------------------------------------

#define MAX_N 201
vector<int> map[MAX_N];

int cow[MAX_N];
int area[MAX_N];
bool visit[MAX_N];

bool fun(int s) {
	// s번 소는 방문
	visit[s] = true;
	for (int i = 0; i < map[s].size(); i++) {
		// 해당 지역이 비었거나
		// 그렇지 않다면
		// 현재 가려고 하는 위치의 소가 처리 되있지 않고
		// &&
		// 처리 되지 않은소가 다른 지역으로 옮겨갔다면 ( true가 return 된다 )
		if (area[map[s][i]] == -1 || (!visit[area[map[s][i]]] && fun(area[map[s][i]]))) {
			cow[s] = map[s][i];
			area[map[s][i]] = s;
			return true;
		}
	}
	// 소를 현재 위치에서 이사시킬 수 없는 경우
	return false;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int N, M; cin >> N >> M;
	
	for (int i = 1; i <= N; i++) {
		int s; cin >> s;
		for (int j = 0; j < s; j++) {
			int data; cin >> data;
			map[i].push_back(data);
		}
	}
	memset(cow, -1, sizeof(cow));
	memset(area, -1, sizeof(area));
	int ans = 0;
	for (int i = 1; i <= N; i++) {
		// 1번 소 부터 차례대로 넣는다 ( 플로우 형식이기 때문에 그냥 차례대로 확인해도 상관없다 )
		if (cow[i] == -1) {
			memset(visit, false, sizeof(visit));
			if (fun(i)) ans++;
		}
	}
	cout << ans << endl;
}

---

기타