<링크>

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번말이 들어갈때>

 방번호

2

3

4

5

말번호

 

1

 

 

 

5번방에는 아직 안가봐도 된다. 걍 2번방이 비어있으니깐 ㅇㅋ여기다 이러고 다음말로 넘기면된다.

<2번말이 들어갈때>

 방번호

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로 체크하는 이유는

이미 밀린놈은 방에 없는걸로치는데 계속 밀어내면 무한루프에 빠지기 때문이다.

+ Recent posts