[Python3] 11376 열혈강호 2 - 플래티넘 4

• 2023.3.13 포스팅 기준 solved.ac 문제 등급 :  플래티넘 4
• 단계별로 풀어보기 -> 이분매칭
• 알고리즘 분류
  • 이분 매칭

<링크>
https://www.acmicpc.net/problem/11376

11376번: 열혈강호 2

시간제한	메모리제한
4 초	256 MB

 

---

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

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

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

 

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

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

 

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

 

<예제 입력 1>

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

<예제 출력 1>

4

 

---

<풀이 접근>

이 문제는 지난번 풀었던 [11375 열혈강호] 에서 이어지는 문제다. 
https://qodelog.tistory.com/14

[Python3] 11375 열혈강호 - 플래티넘 4

위 문제와 다른 점은, 한 직원이 두 개의 일을 맡을 수 있다는 것.
단순히 한 직원을 두명인 셈 치거나, 직원이 담당할 수 있는 두개의 일 slot으로 매칭을 수행하면 된다.

아래의 소스코드를 보면 알겠지만, 이전 문제의 풀이와 거의 똑같이 작성하면 된다.

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

n, m = map(int, input().split())
jobs = [[]] + [[*map(int,input().split())][1:] for _ in range(n)]
matched = [0 for _ in range(m+1)]
res = 0


def dfs(tup):
    a, b = tup # a직원의 b번째 일을 매칭.
    if not visited[a]:
        visited[a] = True
        for job in jobs[a]:
            if matched[job] == a:
                continue
            if matched[job] == 0 or dfs(matched[job]):
                matched[job] = (a,b)
                return True
    return False


for i in range(1,n+1): # i번째 직원에 대해,
    for j in (0,1): # 해당 직원이 담당 할 수 있는 일 [0],[1] 슬롯으로 이분매칭을 수행.
        visited = [False]*(n+1)
        if dfs((i,j)):
            res += 1
        
print(res)

[11375 열혈강호]를 통해 이미 이분매칭을 접해 본 사람들에겐 어렵지 않은 문제일 것이다.

---

이전 문제와 마찬가지로, 호프크로프트-카프 알고리즘으로도 풀어볼 수 있다.
이 역시, 이전 문제를 통해 호프크로프트-카프 알고리즘을 이해했다면 특별히 신경써야 할 점이 없다.
지난 문제에서 제출한 코드를 토대로 약간만 고쳐주면 된다. 

import sys
from collections import deque
input = sys.stdin.readline
INF = sys.maxsize

# 호프크로프트 카프 bfs.
# aMatch[node]를 array로 만들어 연결의 개수를 관리하자.
# aMatch의 len()이 2가 아닌지만 확인해도 2개를 초과해 append될 일이 없다.
# >> 하나의 재귀적인 dfs 시행에서는 한 노드에 새로운 연결이 반드시 한 개만 생길 수 있고,
# >> 해당 dfs 재귀가 끝나면 다음번 bfs에서 연결이 2개임을 확인하고 새로운 연결을 설정할 queue에 추가되지 않게된다.
def bfs():
    queue = deque()
    for node in range(1, n+1):
        if len(aMatch[node]) < 2: # 매칭이 2개가 아니면 level 0. 
            level[node] = 0
            queue.append(node)
        else:
            level[node] = INF
    level[0] = INF

    while queue:
        a = queue.popleft()
        if level[a] < level[0]: 
            for b in edges[a]: 
                if level[bMatch[b]] == INF and len(aMatch[bMatch[b]]) < 2:
                    level[bMatch[b]] = level[a] + 1
                    queue.append(bMatch[b])
    return level[0] != INF

# 호프크로프트 카프 dfs. 달라진 것이 없다.
# bfs를 거친 후, a노드보다 level이 1 높은 다른 노드 a'에 dfs를 시도할 수 있음이 보장되어 있다.
# (a'에 연결 가능한 b가 있어 연결이 생성될 것이라 보장하는 것이 아니다.)
# (단지 a'에 2개 미만의 연결이 있어 탐색을 진행해도 괜찮음을 말하는 것.)
def dfs(a): 
    if a:
        for b in edges[a]:
            if level[bMatch[b]] == level[a] + 1 and dfs(bMatch[b]):
                aMatch[a].append(b)
                bMatch[b] = a
                return 1
        level[a] = INF
        return 0
    return 1


def Hopcroft_Karp():
    count = 0
    while bfs():
        for i in range(1, n+1): # i번 직원에 대해,
            for _ in range(2): # 최대 2개의 일을 매칭.
                if len(aMatch[i]) < 2:
                    count += dfs(i)
    print(count)

if __name__ == "__main__":
    n, m = map(int, input().split())
    edges = [[]]+[[*map(int, input().split())] for _ in range(n)]
    aMatch = [[] for _ in range(n+1)]
    bMatch = [0 for _ in range(m+1)]
    level = [INF for _ in range(n+1)]

    Hopcroft_Karp()

 

이번에도 두 가지의 방법으로 문제를 풀어 보았다.
각각의 코드를 제출한 결과는 아래와 같다. PyPy3로 제출한 것이 이분매칭이고, Python3로 제출한 것은 호프크로프트-카프이다. Python3로 제출했음에도 PyPy3보다 빠르다! 호프크로프트-카프 알고리즘의 강력함을 볼 수 있다.

11376 열혈강호 2 제출 결과.

---

<마무리>
아쉽게도 이 문제를 이분매칭으로 풀어 Python3로 제출한 것은 시간 초과를 보았다. PyPy3로 제출해도 2204ms가 걸릴 정도이니 당연한 듯 싶다. 아무래도 for문에서, 혹은 array 처리과정에 최적화가 필요할 듯 싶다.