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

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

 

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

11375번: 열혈강호

시간제한	메모리제한
2 초	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
1 1
2 2 3
3 3 4 5
1 1

<예제 출력 1>

4

 

---

<풀이 접근>

이분매칭으로 문제를 푸는 것은 생각보다 어렵지 않다.
이분매칭의 수행 과정을 간략히 말하자면, 아래와 같이 말할 수 있다.

1. 어떤 그래프의 정점들을 두 그룹으로 나누어 이분그래프로 나타내고 두 그룹을 각각 A, B라 한다.
2. A그룹의 정점들을 순차적으로 방문하며, 정점의 간선 정보를 토대로 B그룹의 정점과 일대일로 연결한다. 이 때, 한 시행의 시작부터 끝을 "순차방문"이라고 하겠다. 매 순차방문마다 특정 그룹 정점의 방문 여부를 초기화하고 기록한다.
   A그룹의 정점 a에서부터 순차방문을 시작하여 최초로 접근 가능한 B그룹의 정점 b가 아무 정점과도 연결되어 있지 않으면 정점 a와 정점 b를 연결한다. 정점 b가 이미 A그룹의 또 다른 정점 a'에 연결되어 있을 때, 아래와 같이 처리한다.
   
   • 정점 a'를 B그룹의 새로운 정점 b'에 연결하고 a와 b를 연결시킨다. 이 때, b'에 이미 연결이 존재했다면 연쇄적으로 새로운 매칭을 찾는다. 
   • 정점 a'에서 새로운 연결이 불가능한 경우, a'와 다른 간선으로 연결된 B그룹의 정점을 조회한다. 다른 간선이 없거나 모든 간선에서 새로운 연결이 불가능하면(즉, 해당 회차 순차방문에서 이미 방문한 정점을 재방문 한 경우) 정점 a의 매칭을 건너뛴다. 
3. A그룹의 모든 정점에 대해 매칭이 끝나면, 이 때의 매칭이 최대매칭이다.

이 문제와 이분매칭에 대한 자세한 설명은 아래의 링크로 대체하겠다.
https://m.blog.naver.com/kks227/220807541506

이분 매칭(Bipartite Matching)

아래는 이분매칭으로 작성한 소스코드이다.
백준에 제출할때 Python3로 제출하려면 sys.setrecursionlimit을 적당히 늘려주고 제출해야 한다.

# BOJ 11375 열혈강호(이분매칭)
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
# jobs[a] = 직원 a가 할 수 있는 일의 목록.
jobs = [[]]+[[*map(int, input().split())][1:] for _ in range(n)]
# matched[j] = 일 j와 매칭된 직원의 번호를 저장. 초기값 0은 매칭된 직원이 없는 것.
matched = [0 for _ in range(m+1)]
res = 0

# 직원 a에 가능한 새로운 매칭을 찾는다.
def dfs(a):
    for job in jobs[a]:
        if visited[job]:
            continue
        visited[job] = True
        # matched[job]은 job에 이미 매칭되어 있던 직원.
        if matched[job] == 0 or dfs(matched[job]): 
        	# 기존 매칭이 없거나, 기존 매칭된 직원에 새로운 일을 매칭 가능하면, a에게 job을 매칭한다.
            matched[job] = a
            return True
    return False

# 직원 번호 1부터 n까지 일을 매칭한다.
for i in range(1,n+1):
    visited = [False]*(m+1)
    dfs(i)

print(len(matched)-matched.count(0))

결과는 대략 아래와 같이 나온다. 

 

백준 11375 이분매칭 제출 결과

---

동일한 문제를 호프크로프트-카프 알고리즘을 이용해 시간을 단축시킬 수 있다. 
호프크로프트-카프 알고리즘과 11375-열혈강호 문제 시리즈 풀이에 관해 더 자세한 설명은 아래 링크의 블로그 포스트를 참고하길 바란다.
https://jaeseo0519.tistory.com/m/86

[Python] 11375 / 11376 / 11377 / 11378 - 열혈강호 (플래티넘3, 4) : 미해결

위 포스팅과 더불어 많은 호프크로프트-카프 알고리즘을 다룬 글들을 찾아봐도 이해하기는 쉽지 않았다. 
코드를 분석해보고, 직접 테스트케이스를 만들어 손으로 알고리즘의 수행을 따라가보고서야 이해할 수 있었다. 

아래는 위 포스팅의 코드를 토대로 공부하며 내 방식의 명명법과 주석을 붙인 코드이다.
호프크로프트-카프 알고리즘에 대한 자세한 설명은 기회가 된다면 추 후 제대로 정리하여 덧붙이도록 하겠다. 

# BOJ 11375 열혈강호(호프크로프트-카프)
import sys
from collections import deque
input = sys.stdin.readline
INF = sys.maxsize

# 호프크로프트-카프 bfs. A 그룹의 각 정점에 레벨을 매긴다.
def bfs():
    queue = deque()
    for cur in range(1, n+1):
        if aMatch[cur] == 0: # cur노드가 아직 매칭 되지 않았다면 level 0.
            level[cur] = 0
            queue.append(cur) # 매칭되지 않은 정점은 탐색 시작 위치이므로 queue에 추가.
        else:
            level[cur] = INF # 이미 매칭된 A그룹의 정점은 거리 INF로 초기화.
    level[0] = INF # 0번 노드는 네트워크 그래프의 시작 노드이자 A그룹 노드인 셈.

    while queue: # group A의 각 정점 a에 0, 1, 2, 3, ...으로 증가하는 레벨을 매김.
        a = queue.popleft()
        if level[a] < level[0]: # 아직 a 노드의 level 갱신이 안 됐을 때,
            for b in edges[a]: # a 노드의 인접 b 노드에 대하여,
                if level[bMatch[b]] == INF: # b와 매칭된 group A의 노드 a'가 아직 갱신되지 않았다면,
                    level[bMatch[b]] = level[a] + 1 # a'노드의 레벨은 a노드 레벨+1 (잠재적 증가경로)
                    queue.append(bMatch[b])
    return level[0] != INF
    # bMatch의 모든 초기값이 0이므로 bfs 실행시 A그룹의 0번 노드는 level 1이 되지만, 
    # dfs에서는 처리되지 않으므로 신경쓰지 않는다. 
    # 마지막 bfs 시행에서 최대매칭에 도달할 경우 0번 노드에 접근하지 않으므로 level[0] != INF는 False를 리턴한다.
    # >> 최대매칭이 아니라면, A그룹의 a노드에 연결된 B그룹의 b노드에서 bMatch[b] 인 0번 노드에 접근해 level이 INF가 아니게 되어 True가 리턴되고,
    # >> 최대매칭이라면, level이 0인 A그룹의 노드가 없거나, a에서 접근가능한 b노드는 이미 매칭이 되어 있으므로 0번 노드에 접근하지 못 하게 된다.

# 호프크로프트-카프 dfs. 증가경로를 찾는 방향으로 기존 매칭을 갱신한다. 증가경로가 없는 경우 False리턴.
#   (이분매칭처럼, 어떤 정점의 매칭이 바뀌면 기존에 매칭되어있던 짝-정점에서부터 연쇄적으로 새 매칭이 이루어진다.)
#   (따라서 총 매칭이 1만큼 늘어나는 방향으로 진행하고, 매칭이 늘어날 수 없으면 진행되지 않는다.)
def dfs(a): 
    if a: # a can't be 0.
        for b in edges[a]: 
        # A group의 a 노드와 연결된 B group의 노드 b에 대해, 
        # b에 이미 연결된 a'과 a의 레벨 차가 1이면서 (즉, a-b-a' 관계이고)
        # 이 a' 노드가 새로운 매칭이 가능하여 dfs(a')를 수행하면 a'-b'가 매칭될 때, (즉, a-b-a'-b' 증가경로가 존재)
        # 기존 매칭 a'-b에 증가경로 a-b-a'-b'를 적용하여 a-b와 a'-b'로 매칭을 갱신한다.
            if level[bMatch[b]] == level[a] + 1 and dfs(bMatch[b]):
                aMatch[a] = b 
                bMatch[b] = a
                return 1
        level[a] = INF # 갱신 불가능한 노드는 level 정보가 쓸모 없으므로 INF로 수정.
        return 0
    return 1


def Hopcroft_Karp():
    cnt = 0
    while bfs(): # bfs에서 현재 매칭이 최대매칭인지 아닌지를 판단한다. 최대매칭이 아니면 True이고 while-loop로 진입. 
        for idx in range(1, n+1):
            if aMatch[idx] == 0:
                cnt += dfs(idx) # 현재 정점이 아직 매칭되지 않았으면, 새 매칭을 진행한다.
    print(cnt)

if __name__ == "__main__":
    n, m = map(int, input().split())
    # edges[i][j] = A그룹 i번 노드와 B그룹 j번 노드 사이의 간선 정보를 저장.
    edges = [[]]+[[*map(int, input().split())][1:] for _ in range(n)]
    aMatch = [0 for _ in range(n+1)] # group B와 연결된 group A의 정점 정보
    bMatch = [0 for _ in range(m+1)] # group A와 연결된 group B의 정점 정보
    level = [INF for _ in range(n+1)] # group A의 각 정점의 level

    Hopcroft_Karp()

 

아래는 호프크로프트-카프 알고리즘으로 작성한 코드를 제출한 결과이다.

11375 열혈강호 호프크로프트-카프 제출 결과.

Python3로 제출한 것은 약 12분의 1의 시간으로 줄었고, PyPy3로 제출한 것도 약 절반 가량의 시간으로 줄었다.

 

---

<마무리>
11375번을 시작으로 열혈강호 시리즈는 4개의 문제가 있다.
저마다 조금씩 다른 조건으로 생각할 거리를 주거나, 다른 알고리즘으로 풀 것을 유도하고 있다. 

이 문제 덕분에 호프크로프트-카프 알고리즘을 접하게 되었고, 이해하기까지 시간은 좀 걸렸지만 즐거운 경험이 되었다.

다음에는 11376번 열혈강호2 문제를 풀어 볼 계획이다.