백준 온라인 저지, 이분매칭 / 9576번: 책나눠주기 (파이썬 / 백준 골드문제)

문제

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

문제 정의

백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 정수 번호를 중복되지 않게 매겨 두었다.
조사를 해 보니 책을 원하는 서강대학교 학부생이 총 M명이었다. 백준이는 이 M명에게 신청서에 두 정수 a, b (1 ≤ a ≤ b ≤ N)를 적어 내라고 했다. 그러면 백준이는 책 번호가 a 이상 b 이하인 책 중 남아있는 책 한 권을 골라 그 학생에게 준다. 만약 a번부터 b번까지의 모든 책을 이미 다른 학생에게 주고 없다면 그 학생에게는 책을 주지 않는다.
백준이가 책을 줄 수 있는 최대 학생 수를 구하시오.

입력

첫째 줄에 테스트 케이스의 수가 주어진다.
각 케이스의 첫 줄에 정수 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 1,000)이 주어진다. 다음 줄부터 M개의 줄에는 각각 정수 ai, bi가 주어진다. (1 ≤ ai ≤ bi ≤ N)

출력

각 테스트 케이스마다 백준이가 책을 줄 수 있는 최대 학생 수를 한 줄에 하나씩 출력한다.

예제 입력 1

1
2 3
1 2
1 2
1 2

예제 출력 1

2

접근 방법

- DFS를 통해 이분매칭을 구현해 책을 나눠줄 수 있는 최대 학생 수를 출력한다.

코드

# https://www.acmicpc.net/problem/9576
# 접근 방법
# DFS를 통해 이분매칭을 구현해 책을 나눠줄 수 있는 최대 학생 수를 출력한다.
import sys

def dfs(x):
    if visited[x]:
        return False
    visited[x] = True
    for i in s[x]:
        if not d[i] or dfs(d[i]):
            d[i] = x
            return True
    return False

input = sys.stdin.readline
for tc in range(int(input())):
    n, m = map(int, input().split())
    d = [0 for _ in range(n+1)] # 책
    s = [[] for _ in range(m+1)] # 학생이 선호하는 책 번호 저장
    for i in range(1, m+1):
        a, b = map(int, input().split())
        for j in range(a, b+1):
            s[i].append(j) # 각 학생이 선호하는 책의 번호 저장
    for i in range(1, m+1):
        visited = [False for _ in range(m+1)] # 책(d)에 대한 방문 처리
        dfs(i)
    print(sum([1 for x in d if x > 0]))