일꾼과 일감 짝짓기
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
일꾼 workers명(0번 ~ workers - 1번)과 일감 tasks개(0번 ~ tasks - 1번)가 있습니다.
can[i] = [w, t]는 w번 일꾼이 t번 일감을 할 수 있다는 뜻입니다.
일꾼 한 명은 일감을 최대 하나만 맡고, 일감 하나도 최대 한 명에게만 맡깁니다. 일꾼이 할 수 있는 일감만 맡길 때, 동시에 처리할 수 있는 일감의 최대 개수를 반환하세요.
입출력 예
| workers | tasks | can | result |
|---|---|---|---|
3 | 3 | [[0, 0], [0, 1], [1, 0], [2, 1]] | 2 |
3 | 3 | [[0, 0], [0, 1], [1, 1], [1, 2], [2, 0]] | 3 |
2 | 4 | [] | 0 |
입출력 예 설명
예 1 — 2번 일감은 아무도 할 수 없고, 0번·1번 일감만 맡길 수 있으므로 최대 2개입니다.
예 2 — 0번 일꾼에게 1번, 1번 일꾼에게 2번, 2번 일꾼에게 0번 일감을 맡기면 3개 모두 처리됩니다. 0번 일꾼에게 먼저 0번 일감을 주면 2번 일꾼이 할 일이 없어지므로, 배정을 바꿔 가며 찾아야 합니다.
예 3 — 할 수 있는 일이 하나도 없습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(workers: int, tasks: int, can: int[][]) → int
제한 사항
-
workers,tasks -
can.length -
wworkers,ttasks. 같은 쌍이 여러 번 주어질 수 있습니다.
기대 복잡도
- 시간
- O(E * sqrt(V))
- 공간
- O(V + E)
입출력 예
| workers | tasks | can | 기대 출력 |
|---|---|---|---|
3 | 3 | [[0,0],[0,1],[1,0],[2,1]] | 2 |
3 | 3 | [[0,0],[0,1],[1,1],[1,2],[2,0]] | 3 |
2 | 4 | [] | 0 |
힌트
힌트
이분 그래프의 최대 매칭 문제입니다. 핵심은 증가 경로입니다.
아직 일이 없는 일꾼 w에서 출발해 "할 수 있는 일감 t로 가고, t를 이미 맡은 일꾼이 있으면 그 일꾼이 다른 일감을 맡을 수 있는지 다시 찾는" 과정을 반복합니다.
비어 있는 일감에 도착하면 경로를 따라 배정을 한 칸씩 바꿔서 매칭을 1 늘릴 수 있습니다.
def try_assign(w): # 이번 탐색에서 방문한 일감은 다시 보지 않음
for t in adj[w]:
if visited[t]: continue
visited[t] = True
if owner[t] == -1 or try_assign(owner[t]):
owner[t] = w
return True
return False
일꾼마다 한 번씩 이 탐색을 하면(쿤 알고리즘) 이고, 여러 증가 경로를 BFS로 층을 나눠 한꺼번에 찾는 호프크로프트-카프 알고리즘은 입니다. 깊은 재귀가 걱정되면 반복문으로 바꾸세요.
복잡도 목표
인접 행렬을 매번 전부 훑으며 증가 경로를 하나씩 찾는 풀이는 효율성 테스트에서 시간 초과가 납니다. 인접 리스트를 쓰세요.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1132 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 12 | 판정만 |
| performance | 60 | 4 | 판정만 |