[백준/11376] 열혈강호 2 (Python)

Problem : https://www.acmicpc.net/problem/11376

11376번: 열혈강호 2

 

Difficulty : Platinum 4

 

Status : Solved

 

Time : 00:09:46

 

---

 

문제 설명

 

 

강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다.

각 직원은 최대 두 개의 일을 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다.

각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

 

첫째 줄에 직원의 수 N과 일의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다.

 

출력

 

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

 

입력 예시

 

5 5
2 1 2
2 1 2
2 1 2
2 4 5
0

 

출력 예시

 

4

 

 

---

 

풀이

 

어제 풀이했던 문제와 동일하게 이분 매칭으로 도전해 볼 법 하다.

 

2023.12.07 - [알고리즘 문제/백준] - [백준/2188] 축사 배정 (Python)

[백준/2188] 축사 배정 (Python)

 

단 여기서는 한 사람당 2개까지의 일을 맡을 수 있다. 그런데 간단하게 생각해보면, visited 초기화 후 dfs호출을 두 번 해주기만 해도 된다. 허허...

 

p.s. dfs 함수 호출 자체에 시간이 매우 오래 소요되므로, 우선 추가적인 매칭 과정 없이 할 수 있는 일 (works[idx] == -1) 부터 탐색하는 게 훨씬 싸게 먹힌다. 얼핏 보면 코드가 깔끔해 보이지 않을 수 있는데, 이런 이유로 dfs 내부 for문을 중복해서 사용했다.

 

 

풀이 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N, M = map(int, input().split())
worker_list = [tuple(map(int, input().split()))[1:] for _ in range(N)]
works = [-1]*(M+1)
ans = 0

def dfs(worker) :
  if visited[worker] :
    return False
  visited[worker] = True

  for work in worker_list[worker] :
    if works[work] == -1 :
      works[work] = worker
      return True
  for work in worker_list[worker] :
    if dfs(works[work]) :
      works[work] = worker
      return True
  return False

for i in range(N) :
  visited = [False]*N
  if dfs(i) :
    ans += 1
  visited = [False]*N
  if dfs(i) :
    ans += 1
  if ans == M :
    break

print(ans)

풀이 완료!