9576 책 나눠주기 (백준, python3)

 

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

문제

백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 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개의 줄에는 각각 정수 a_i, b_i가 주어진다. (1 ≤ a_i ≤ b_i ≤ N)

 

출력

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

 

---

풀이

책을 몇 권을 받든 상관 없고 1권씩만 줘도 "책을 준 학생"이기 때문에 가능한 경우에 1권씩만 주는 것이 많은 학생에게 나눠주기 좋다. 따라서 학생-책으로 나누어지는 이분 그래프에서 가장 많은 매칭을 만드는 것이 이 문제의 답이 된다.

 

1. 이분매칭(Bipartite Matching)

모든 이웃한 정점을 서로 다른 2가지의 색으로 칠할 수 있는 그래프를 이분그래프라고 한다. 그래서 색칠을 끝낸 이분 그래프를 색깔별로 나누어두면 두 그룹 사이에서 사랑의 짝대기를 한 모양새가 되는데 이 때, 양 그룹 간 1대1 연결을 하나의 매칭이라고 하고, 매칭이 성사되었을 때 연결된 두 정점의 다른 간선을 모두 무시하는 작업을 최대한 많이 수행하는 것이 이분매칭 알고리즘이다.

 

예를 들어

이런 이분그래프가 있다고 하자. 양 그룹에 5개의 원소가 있고 흰색 선은 매칭 가능한 간선들을 이어놓은 것이다. 먼저 왼쪽 그룹 1번을 1번에 연결할 수 있다. 이렇게 매칭 성공.

이제 왼쪽 2번을 연결해봐야 하는데 우선 가능한 간선을 타고 1번으로 왔더니 오른쪽 1번은 이미 왼쪽 1번이랑 매칭이 되어있다. 이 매칭을 타고 거슬러와서 왼쪽 1번의 매칭을 다른 곳으로 옮길 수 있나 봤더니 오른쪽 3번으로 매칭이 된다. 그럼 왼쪽 2번을 오른쪽 1번과 매칭하고 왼쪽 1번의 기존 매칭을 끊고 오른쪽 3번으로 매칭시킨다.

같은 방법으로 왼쪽 3번의 매칭, 4번의 매칭까지 성공했다. 왼쪽 5번의 매칭을 시작하기 위해 오른쪽 4번으로 왔다. 이미 오른쪽 4번은 매칭이 되어있으니 거슬러 올라가봐야 한다.

5에서 4, 4에서 3, 3에서 2, 2에서 2, 2에서 1, 1에서 1, 1에서 3, 3에서 4까지 거슬러 올라가봤는데 왼쪽 4에서 더 이상 거슬러 올라갈 길도, 새로운 매칭이 가능한 곳도 없다. (이전의 모든 왼쪽 그룹 원소들이 새로운 매칭이 만들어지지 않았기 때문에 여기까지 거슬러 왔다.) 그러면 왼쪽 5를 오른쪽 4와 매칭시키는 작업은 포기하고 다음으로 넘어간다.

왼쪽 5는 오른쪽 5와 매칭이 된다. 이렇게 양 그룹의 매칭이 끝났고 최대 매칭은 5개다.

 

여기까지의 과정을 보면 딱 느낌이 오는데 이 알고리즘은 dfs이며 최악의 경우, 이전에 성사된 모든 매칭을 다 거슬러 올라가 확인해야 한다. 따라서 최악의 경우 시간 복잡도는 전체 정점 V, 전체 간선 E에 대해 O(VE)의 시간 복잡도를 갖는다. (모든 정점에서 모든 간선을 다 돌아봄)

 

2. 적용

예제를 보면 모든 학생이 모든 책을 다 원한다. 이 경우 책 1에서 출발한 매칭이 먼저 1에 닿고, 다음 책 2에서 출발한 매칭이 1의 매칭을 끊고 학생 1과 연결되며 책 1은 2로 연결된다. 이 때 연결된 매칭을 타고 올라가는 dfs가 필요하다.

 

따라서 이 알고리즘을 구현하기 위해서는 오른쪽 그룹(편의상 오른쪽에 뒀는데 선택되는 쪽으로 보면 됨)이 누구(왼쪽 정점)에게 선택되었는지 기록해야 하고, dfs는 이걸 기반으로 역추적을 해 나가며 다른 매칭의 가능성을 봐야 한다.

 

굉장히 정리가 잘된 라이님의 블로그 글(사실 최대유량부터 이 분이 써놓은 글 보고 다 배웠다. 정리 너무 깔끔함..)

이분 매칭(Bipartite Matching)

 

 

정답 코드

# 9576: 책 나눠주기
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def match(k):
    if visit[k]: return False
    visit[k] = True
    for t in graph[k]:
        if stud[t] == -1:
            stud[t] = k
            return True
    for t in graph[k]:
        if stud[t] >= 0 and match(stud[t]):
            stud[t] = k
            return True
    return False

T = int(input())
for _ in range(T):
    N,M = map(int,input().split())
    graph = [[] for _ in range(N+1)]
    count = 0

    stud = [-1]*(M+1)

    # 원하는 책 이어주기
    for m in range(1,M+1):
        a,b = map(int,input().split())
        for i in range(a,b+1):
            graph[i].append(m)

    # 매칭
    for i in range(1,N+1):
        visit = [False]*(N+1)
        if match(i): count += 1
        if count == M: break

    print(count)