[백준/11377] 열혈강호 3 (Python)

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

11377번: 열혈강호 3

 

Difficulty : Platinum 3

 

Status : Solved

 

Time : 00:06:00

 

---

 

문제 설명

 

 

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

각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다. 단, N명 중에서 K명은 일을 최대 2개할 수 있다.

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

 

 

입력 및 출력

 

입력

 

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

 

출력

 

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

 

입력 예시

 

5 5 1
3 1 2 3
3 1 2 3
1 5
1 5
1 5

 

출력 예시

 

4

 

 

---

 

풀이

 

어제 풀이한 문제의 변형판. 이분 매칭의 응용 문제라고 볼 수 있다.

 

2023.12.08 - [알고리즘 문제/백준] - [백준/11376] 열혈강호 2 (Python)

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

 

위 문제에서 2개 일을 할 수 있는 사람은 dfs를 두 번 호출하면 된다는 점을 이용했다. 여기서는 모든 사람이 아닌 K명의 사람만이 2개 일을 할 수 있으다. 따라서 DFS를 호출하는 2번째 순회를 돌되, 이 순회에서 K번 매칭이 발생하면 순회를 정지해야 한다.

 

또한 지금까지는 각 dfs 호출 전 visited 배열을 초기화하는 과정을 거쳤고, 이것이 시간복잡도 및 공간복잡도상의 비효율성을 야기했다. 이 제출 코드의 도움을 받아(https://www.acmicpc.net/source/66456020) 이를 개선할 수 있었다.

 

visited 배열의 생성은 단 한번이면 충분하다. 또한 DFS 함수 내부에서 DFS 함수를 다시 재귀적으로 호출할 때에 visited 배열을 검사하게 된다. 만약 DFS 호출 시에도 매칭에 실패한다면, 그 노드를 검사했을 때 더 이상의 갱신이 불가능하다는 의미이다. 따라서 이 때는 visited[node]를 그대로 True로 둔다. 매칭이 성공한다면, 또 그 노드를 검사했을 때 갱신이 가능한지의 여부를 아직은 알 수 없으므로 visited[node]를 False로 다시 바꾼다.

 

풀이 코드

import sys

input = sys.stdin.readline

N, M, K = map(int, input().split())
work_list = []
for _ in range(N):
  n, *lst = map(int, input().split())
  if not n:
    N -= 1
  else:
    work_list.append(lst)
work = [-1] * (M + 1)
visited = [False] * N
ans = 0

def dfs(node):
  for w in work_list[node]:
    if work[w] == -1:
      work[w] = node
      return True
  for w in work_list[node]:
    if visited[work[w]]:
      continue
    visited[work[w]] = True
    if dfs(work[w]) :
      visited[work[w]] = False
      work[w] = node
      return True
  return False

res_0, res_1 = 0, 0
for i in range(N):
  if dfs(i):
    res_0 += 1
  if res_0 == M:
    break

for i in range(N):
  if len(work_list[i]) == 1:
    continue
  if dfs(i):
    res_1 += 1
  if res_0 + res_1 == M or res_1 == K:
    break
print(res_0 + res_1)

풀이 완료!