백준_2188_축사 배정

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

2188번: 축사 배정

 

해결방법

- 이분 매칭을 이용한다.

 

실수했던 부분

- 축사를 배정함에 있어 우선순위가 있는것이 아니라 그냥 최대한 많이 배정하는 것인데 나는 우선순위가 있는 것처럼 풀었었다.

- 위의 문제를 해결하기 위해 각 소들이 원하는 축사에 대한 정보를 pop()으로 꺼내던 것을 for문을 돌았다.

 

코드

N, M = map(int, input().split())

 

info = []

group_a, group_b = [-1] * N, [-1] * M

 

for i in range(N):

    list_tmp = list(map(int, input().split()))

    info.append(list_tmp[1:])   #차례대로 입력이 들어오기 때문에 슬라이싱을 해준다.

 

def dfs(a):

    visit[a] = True

    for b in info[a]:   #우선순위로 배정하는게 아니므로 pop을 하는게 아니라 for문을 돈다.

        b -= 1

        if group_b[b] == -1 or not visit[group_b[b]] and dfs(group_b[b]):   #연결이 되어있지 않거나 group_a에서 group_b로 갈 곳이 남아있는 경우

            group_a[a], group_b[b] = b, a   #축사 배정

            return True

    return False

 

count = 0

for i in range(N):

    if group_a[i] == -1:

        visit = [False] * N

        if dfs(i):

            count += 1

    

print(count)