(Python/플4)백준알고리즘 11375번 : 열혈강호

문제 바로가기 

문제:

강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 자신이 할 수 있는 일들 중 한 개의 일만 담당할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다. 각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 직원의 수 N과 일의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다.

출력:

첫째 줄에 강호네 회사에서 할 수 있는 일의 개수를 출력한다.

 

풀이:

이 문제는 이분매칭이라는 문제이다.

 

이 문제를 풀면서 이분매칭을 잘 몰랐는데 오늘 좀 잘 알아가게 된거 같다.

https://velog.io/@woolzam/%EC%9D%B4%EB%B6%84-%EB%A7%A4%EC%B9%AD

[알고리즘] 이분 매칭

https://www.youtube.com/watch?v=PwXNTA0rpXc&t=9s

 

이것들을 통해서 공부했다.

 

일단 틀린코드

import sys
from collections import defaultdict

n, m = map(int, sys.stdin.readline().rstrip().split())

# 딕셔너리로 직원과 가능한 일을 저장
dic = defaultdict(list)

for i in range(n):
    lst = list(map(int, sys.stdin.readline().rstrip().split()))
    # 직원이 할 수 있는 일이 있을 경우에만 추가
    if len(lst) > 1:
        dic[i + 1] = lst[1::]

# 정렬: 길이 내림차순, 값 내림차순
dic = sorted(dic.items(), key=lambda item: (-len(item[1]), -max(item[1]) if item[1] else float('-inf')))

# 결과 변수
res = 0

# 일을 담당한 사람을 기록할 딕셔너리
workdic = defaultdict(int)

while dic:
    people, works = dic.pop()

    # 할 수 있는 일 중에서
    for work in works:
        # 그 일이 아직 처리되지 않았으면
        if work not in workdic:
            # 그 일을 처리하고
            workdic[work] += 1
            # 처리한 일의 수를 증가
            res += 1
            break

# 결과 출력
print(res)

 

다음과 같이하면 가장 좋은 방법은 안 나오기때문에 이분매칭으로 처리해줘야한다.

 

 

 

import sys

sys.setrecursionlimit(100000)
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n, m = map(int, input().split())
task = [list(map(int, input().split()))[1:] for _ in range(n)]
visit = [-1] * (m + 1)


# x번째 사람을 작업에 배정
def dfs(x):
    # x번째 사람이 할 수 있는 작업 i에 대해 반복
    for i in task[x]:
        # i번째 작업이 아직 확인되지 않았다면
        if not check[i]:
            # i번째 작업을 이번 탐색에서 이미 확인했음을 표시 (중복 탐색 방지)
            check[i] = True
            # i번째 작업이 아직 배정되지 않았거나, 이미 배정된 사람이 다른 작업을 맡을 수 있는 경우
            if visit[i] == -1 or dfs(visit[i]):
                # i번째 작업을 x번째 사람에게 배정
                visit[i] = x
                return True
    # x번째 사람이 작업을 맡을 수 있으면 True, 그렇지 않으면 False 반환
    return False


result = 0

for i in range(n):
    check = [False] * (m + 1)
    if dfs(i):
        result += 1
    print(visit)
print(result)