[BOJ 11375] 열혈강호

문제

---

https://www.acmicpc.net/problem/11375

풀이

---

이분 매칭 기본 문제이다.

flow network를 구상하고 최대 flow를 구하는 방식으로도 풀 수 있지만, 간신히 TLE가 안 뜨는 수준으로 통과한다.

그래서 이분 그래프란 점을 이용해 조금 더 간결하게 풀 수 있다.

Edmonds-Karp 알고리즘이 아닌 Ford-Fulkerson 알고리즘을 변형하는데, 우선 그래프는 인접 리스트로 만들었고 a, b란 두 배열을 새로 생성했다.

i번째 왼쪽 노드가 j번째 오른쪽 노드와 연결되어 있으면 a[i] = j이고, b[j] = i이다.

디폴트 값은 0이다.

그 후 1번째 왼쪽 노드부터 n번째 왼쪽 노드까지 각각에 대해 dfs를 돌리는데, dfs(i)의 값은 i번째 왼쪽 노드가 매칭에 성공하면 1, 실패하면 0이다.

dfs 과정은 다음과 같다.

1. i번째 왼쪽 노드를 cur, 이와 연결된 j번째 오른쪽 노드를 nxt라고 하자.

2. nxt가 매칭되지 않은 상태면, cur과 nxt를 매칭 시켜준다.

3. nxt가 매칭되어있고 nxt와 매칭된 왼쪽 노드를 방문한 적 없다면, 이 왼쪽 노드를 다른 오른쪽 노드와 매칭 시켜본다.

4. 매칭에 성공하면 순차적으로 a, b를 갱신시키고 마지막으로 cur과 nxt를 매칭 시켜준다.

참고로, $ O(E \sqrt {V}) $만에 통과하는 Hopcroft-Karp 알고리즘도 있다고 한다.

코드

---

import sys


def dfs(cur):
    visit[cur] = 1
    for nxt in graph[cur]:
        if not b[nxt] or (not visit[b[nxt]] and dfs(b[nxt])):
            b[nxt] = cur
            return 1
    return 0


n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n + 1)]

for i in range(1, n + 1):
    data = list(map(int, sys.stdin.readline().split()))
    for j in range(1, data[0] + 1):
        graph[i].append(data[j])

b = [0] * (m + 1)
ans = 0

for i in range(1, n + 1):
    visit = [0] * (n + 1)
    ans += dfs(i)

print(ans)