<링크>
https://www.acmicpc.net/problem/2188
<소스코드>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #include<stdio.h> #include<vector> #define MAX 201 using namespace std; vector<int> want [MAX]; int visited[MAX]; int room[MAX]; int solve(int); int main() { int N, M; scanf("%d%d", &N, &M); for (int i = 1; i <= N; ++i) { int a, b; scanf("%d", &a); while (a--) { int b; scanf("%d", &b); want[i].push_back(b); } } int ans = 0; for (int i = 1; i <= N; ++i) { fill(visited,visited+N, 0); if (solve(i)) { //for (int j = 1; j <= M; ++j) // printf("%d ", room[j]); //printf("\n"); ++ans; } } printf("%d", ans); } int solve(int c) { if (visited[c]) return 0; visited[c] = 1; for (int w : want[c]) //원하는방에 갈수있는지 체크 { if (!room[w] || solve(room[w])) //방이 비어있거나, 원래있던놈을 밀어낼수있으면 { room[w] = c; return 1; } } return 0; } | cs |
<풀이>
소를 1번소부터 순서대로 원하는 방에 들어갈 수 있는지 체크한다.
들어갈 수 있으면 총원을 늘려준다.
방이 비어있거나, 원래 방에 있던놈을 밀어낼 수 있으면 된다.
경우의 수를 다 셀 필요없이 들어갈수만 있으면 바로 재귀를 끝내버린다.
1번말이 원하는 방 : 2 5
2번말이 원하는 방 : 2 3 4
3번말이 원하는 방 : 1 5
4번말이 원하는 방 : 1 2 5
5번말이 원하는 방 : 2
<1번말이 들어갈때>
방번호 |
1 |
2 |
3 |
4 |
5 |
말번호 |
|
1 |
|
|
|
5번방에는 아직 안가봐도 된다. 걍 2번방이 비어있으니깐 ㅇㅋ여기다 이러고 다음말로 넘기면된다.
<2번말이 들어갈때>
방번호 | 1 | 2 | 3 | 4 | 5 |
말번호 |
| 2 |
|
| 1 |
원래 2번방에있던 1번말을 5번방으로 밀어내고 자기가 들어간다.
<3번말이 들어갈때>
방번호 | 1 | 2 | 3 | 4 | 5 |
말번호 | 3 | 2 | 1 |
1번방이 비어있으니깐 ㅇㅋ개꿀 이러고 들어가면된다.
<4번말이 들어갈때>
원하는 1번방부터 보는데,
1번방에 있던 3번말을 5번방으로 밀어내고
5번방에 있던 1번말을 2번방으로 밀어내고
2번방에 있던 2번말을 3번방으로 밀어낸다.
방번호 | 1 | 2 | 3 | 4 | 5 |
말번호 | 4 | 1 | 2 |
| 3 |
<5번말이 들어갈때>
방번호 | 1 | 2 | 3 | 4 | 5 |
말번호 | 4 | 1 | 2 |
| 3 |
밀고 밀어도 아무도 비켜줄수있는 말이 없으니깐 얘는 방을 차지할 수 없다.
visit로 체크하는 이유는
이미 밀린놈은 방에 없는걸로치는데 계속 밀어내면 무한루프에 빠지기 때문이다.