[BOJ 9496] 조 나누기

문제

---

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

풀이

---

세 개 학년을 두 조로 나누면 한 조는 한 학년, 다른 한 조는 두 학년을 포함하게 된다.

이때 두 학년을 포함한 조의 학생들을 조건을 만족하면서 최대로 만들어주면 된다.

사이가 안 좋은 학생들 사이를 엣지로 이어 이분 그래프에서 생각해 보면, 최대 매칭이 0일 때까지 학생을 줄여야 하므로 maximal independent set의 크기를 구하는 것과 동일하다.

이는 전체 학생 수에서 minimum vertex cover의 크기, 즉 최대 매칭 수를 뺀 것과 같다.

코드

---

import sys


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


n = int(sys.stdin.readline())
data = sys.stdin.readline().strip()
board = [sys.stdin.readline().strip() for _ in range(n)]
ans = float('inf')

for x, y in [('1', '2'), ('1', '3'), ('2', '3')]:
    graph = [[] for _ in range(n)]

    for i in range(n):
        if data[i] == x:
            for j in range(n):
                if (data[j] == y) and (board[i][j] == 'Y'):
                    graph[i].append(j)

    b = [-1] * n
    flow = 0
    for i in range(n):
        visit = [0] * n
        flow += dfs(i)

    ans = min(ans, flow)

print(n - ans)