Funcia
Lv.3bipartite-matchinggraph

일꾼과 일감 짝짓기

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

일꾼 workers명(0번 ~ workers - 1번)과 일감 tasks개(0번 ~ tasks - 1번)가 있습니다. can[i] = [w, t]는 w번 일꾼이 t번 일감을 할 수 있다는 뜻입니다.

일꾼 한 명은 일감을 최대 하나만 맡고, 일감 하나도 최대 한 명에게만 맡깁니다. 일꾼이 할 수 있는 일감만 맡길 때, 동시에 처리할 수 있는 일감의 최대 개수를 반환하세요.

입출력 예

workerstaskscanresult
33[[0, 0], [0, 1], [1, 0], [2, 1]]2
33[[0, 0], [0, 1], [1, 1], [1, 2], [2, 0]]3
24[]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

제한 사항

  • 1≤1 \le workers, tasks ≤3,000\le 3{,}000
  • 0≤E=0 \le E = can.length ≤50,000\le 50{,}000
  • 0≤0 \le w << workers, 0≤0 \le t << tasks. 같은 쌍이 여러 번 주어질 수 있습니다.

기대 복잡도

시간
O(E * sqrt(V))
공간
O(V + E)

입출력 예

workerstaskscan기대 출력
33[[0,0],[0,1],[1,0],[2,1]]2
33[[0,0],[0,1],[1,1],[1,2],[2,0]]3
24[]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

일꾼마다 한 번씩 이 탐색을 하면(쿤 알고리즘) O(V⋅E)O(V \cdot E)이고, 여러 증가 경로를 BFS로 층을 나눠 한꺼번에 찾는 호프크로프트-카프 알고리즘은 O(EV)O(E\sqrt{V})입니다. 깊은 재귀가 걱정되면 반복문으로 바꾸세요.

복잡도 목표

인접 행렬을 매번 전부 훑으며 증가 경로를 하나씩 찾는 O(V3)O(V^3) 풀이는 효율성 테스트에서 시간 초과가 납니다. 인접 리스트를 쓰세요.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251132 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4012판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.