Algorithm Bipartite Matching

알고리듬 Bipartite Matching을 알아보겠습니다.

Bipartite Matching은 이분 매칭으로 한 쪽에서 한 쪽으로 매칭 시키는 것을 말합니다.
​
예를 들어서 의자 앉기를 보죠.
4 사람과 4 개의 의자가 있습니다.

이 사람들이 최대 몇 명까지 의자에 앉을 수 있을까요?

​

정답은 4 명 모두 다 앉을 수 있습니다.

0 -> 0

1 -> 1

2 -> 2

3 -> 3

이렇게 앉으면 됩니다.

이걸 알고리듬으로 어떻게 찾느냐가 문제인데요.

​

​

다음과 같이 풀이합니다.

0 번을 0 번에 앉힙니다.

다음 1 번은 어디 앉을까요?

일단 첫 번째 화살표로 갑니다.

어라... 0 번이 있네요. 0 번이 다른 곳에 앉을 수 있는지 찾아봅니다.

만약 다른 곳에 앉을 곳이 있다면, 0 번이 양보를 해주고 다른 곳으로 갑니다.

만약 다른 곳에 앉을 곳이 없다면, 1 번은 의자에 앉지 못합니다.

다행히 3 번에 앉을 수 있군요!

​

다음, 2 번 앉아 봅시다.

첫 번째 화살표로 갑니다.

없네요. 앉습니다.

자, 마지막 3 번 앉아 봅시다.

어랏... 0 번이 있네요.

이제, 0 번을 다른 곳에 앉혀 봅니다.

1 번이 있네요.

1 번을 다른 곳에 앉혀 봅니다.

2 번이 있네요.

2 번을 다른 곳에 앉혀 봅시다.

오, 마침 2 번 자리가 비었군요.

그럼 이제, 모두 자리에 앉힙니다.

짜잔, 모두 앉았습니다.

​

이 알고리듬의 핵심은 다른 자리에 앉혔을 때, 가능한가 불가능한 가로 판단합니다.

만약 2 번 자리가 비어있지 않았다면, 3 번은 앉을 수가 없는 겁니다.

​

​

파이썬으로 한 번 적어봅시다.

의자와 사람을 나타내는 graph가 있습니다.

함수를 하나 만듭니다.

저는 sitting으로 만들었습니다.

number_of_person에는 사람 수를 number_of_chairs에는 의자 수를 넣습니다.

그리고 현재 앉은 사람을 나타내는 current_sitting_state를 만들고 -1로 초기화합니다.

6 번째 줄처럼 사람 수만큼 앉히기를 시도합니다.

7 번째 줄처럼 다음 사람마다 의자 앉기를 시도했는지를 확인할 리스트를 False로 초기화합니다.

16 번째 줄처럼 앉기가 가능한지 확인할 함수를 만듭니다.

19 번째 줄처럼 해당 사람이 앉고 싶은 의자 리스트를 받아옵니다.

20 번째 줄처럼 의자를 모두 둘러봅니다.

21 번째 줄처럼 만약 앉고 싶은 의자이고, 앉기를 시도하지 않았다면, 23 번째 줄처럼 앉기를 시도했다고 만듭니다.

25 번째 줄처럼 현재 앉아있는 사람이 없거나, 현재 의자에 앉아있는 사람이 다른 곳에 앉을 수 있다면, 29 번째 줄처럼 그 사람을 현재 의자에 앉힙니다.

그리고 True를 반환합니다.

32 번째 줄처럼 만약 앉힐 수가 없다면, False를 반환합니다.

6 번째 줄처럼 total을 만듭니다.

함수에 반환값이 생겼으므로, 9 번째 줄처럼 if 문을 만듭니다.

앉힐 수 있다면, total에 1을 더합니다.

17 번째 줄처럼 total을 반환합니다.

실행해 봅시다.

앉은 과정을 보고 싶다면, 중간중간에 print 문을 넣어줍니다.

17 번째와 24 번째 줄에 넣어줍니다.

끝.

카테고리: Algorithm