[Python - Greedy, Bipartite Matching] 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개의 줄에는 각각 정수 a_i, b_i가 주어진다. (1 ≤ a_i ≤ b_i ≤ N)

📌 출력

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

📌 문제 풀이

👨‍🏫 접근

1. 그리디

이 문제를 어떻게 그리디로 푸나 의문이 들었었다. 이내 해결 방법을 찾을 수 있었는데, 가장 많은 사람이 책을 가져야 하기 때문에, 원하는 범위가 가장 좁은 사람을 우선으로 해서 책을 나눠줘야 더 많은 사람이 책을 나눠받을 수 있음을 알게 되었다. 왜냐하면, 범위가 좁은 사람에 비해 범위가 넓은 사람은 그만큼 책을 자유롭게 고를 수 있기 때문이다. 그렇기 때문에 범위가 좁은 사람 먼저 순회해서 값을 찾아야 한다.

 

범위가 좁은 사람을 알 수 있는 방법은 b를 중심으로 정렬을 해야 한다는 것이다. 어차피 a는 b보다 작으며, b가 작을 수록 범위가 좁은 경향이 있기 때문이다. 그런데 b는 같지만 범위가 더 넓은 사람이 있을 수도 있다. 하지만, 걱정하지 않아도 되는 것이 각 학생의 책을 탐색할 때 오름차순으로 탐색하면 문제가 되지 않기 때문이다.

 

예를 들어, a 학생은 1~3까지의 책을 b 학생은 2~3까지의 책을 원한다고 할 때, 정렬에 따라서 a학생 먼저 책을 준 후 b 학생에게 책을 주게 된다. 이때, a 학생에게 책을 줄 때 가장 번호가 낮은 책부터 주기 때문에 1번 책을 a 학생에게 준다. 그러면 b학생은 2~3까지의 책을 원하기 때문에 아무 영향 없이 그 책을 가질 수 있게 된다.

 

반대로 a를 중심으로 정렬을 한 경우에 문제가 생긴다. 예를 들어 a학생이 1~1, b학생이 1~3, c학생이 2~2를 원한다고 할 때, a 학생이 1번 책 b 학생이 2번 책을 갖게 되어서 c 학생은 책을 갖지 못하게 된다. 따라서, a를 중심으로 정렬을 하는 것은 좋지 않다.

 

하지만, 이것은 학생이 원하는 책을 오름차순으로 탐색했을 경우일 뿐 만약 학생이 원하는 책을 내림차순으로 탐색하면 또 답이 될 수 있다. for문에서 세 번째 매개변수 자리에 -1을 인자로 넣어 거꾸로 탐색하는 것이다. 전체 코드에서 두 가지 스타일 모두 작성해볼까 한다.

 

2. 이분 매칭

이번에 새로운 알고리즘을 배웠는데 바로 이분매칭이다. 이분매칭의 핵심은 이분 그래프와, 단방향 간선 이 두 가지이다. A라는 정점 그룹과 B라는 정점 그룹에서 A -> B로 가는 간선들만 있을 때, 이들을 어떻게 최대한 많이 연결할 수 있을까를 찾아내는 알고리즘이 이분 매칭 알고리즘이다. 이분매칭 알고리즘은 생각보다 어렵지 않고 이해하는 순간 매우 쉽게 느껴진다.

 

예를 들어 아이돌 포토카드를 구매하려는 팬들이 있다고 해보자. 팬들은 총 3명이 있고, 포토카드는 카리나-윈터-지젤로 총 3개의 카드가 있으며 각각 1번, 2번, 3번으로 명명한다.

 

1번 팬은 욕심이 많아서 1, 2, 3번 모두를 원하고 2번 팬은 1번 그리고 3번 팬은 2번을 원한다. 즉, 그림으로 표현하면 아래와 같다.

 

먼저 1번 팬이 1번 포토카드를 원한다고 하면

그리고 2번 팬으로 넘어갔는데 2번 팬과 1번 팬이 원하는 카드가 겹치게 된다.

욕심이 별로 없는 1번 팬은 1번 포토카드말고 2번 포토카드로 방향을 바꾼다.

그 이후 3번 팬의 차례가 되었는데 여기서 또 1번 팬과 원하는 카드가 겹친다.

그래서 1번 팬은 다시 원하는 카드를 3번으로 바꾼다.

이렇게 되면 모든 팬이 사이 좋게 원하는 카드를 선택하게 된다.

 

이런 식으로 한 정점이 다른 정점으로 매칭을 최대로 완료할 수 있다. 이러한 알고리즘을 이분매칭(Bipartite Matching)이라고 한다.

 

간단하게 과정을 다시 살펴보면

1. 새롭게 방문 테이블을 설정한다. A-1번 노드가 B-1번 노드로 연결된다. B-1번 노드는 방문처리 된다. B-1번 노드는 A-1번 노드와 연결됨을 저장한다.
2. 새롭게 방문 테이블을 설정한다. B-1번 노드는 방문처리 된다. A-2번 노드가 B-1번 노드로 연결되려고 하지만 이미 A-1번 노드가 B-1번을 가리킨다. A-1번 노드로 이동한다. A-1번 노드가 가리키는 B-1번 노드는 이미 값을 갖고 있기 때문에 2번 노드로 연결된다. B-2번 노드는 방문처리 된다. A-1번 노드가 매칭된 후에 A-2번 노드는 B-1번 노드를 가리키고, B-1번 노드는 A-2번 노드와 연결됨을 저장한다. 
3. 새롭게 방문 테이블을 설정한다. B-2번 노드는 방문처리 된다. A-3번 노드는 B-2번 노드로 연결되려고 하지만 이미 A-1번 노드가 B-2번을 가리킨다. A-1번 노드로 이동한다. B-1 번 노드는 방문처리 된다 A-1번 노드가 가리키는 B-1번 노드는 A-2를, B-2번 노드는 A-1의 값을 갖고 있기 때문에 3번 노드로 연결된다. B-3번 노드는 방문처리 된다 A-1번 노드가 B-3번 노드와 연결된 후에 A-3번 노드는 B-2번 노드를 가리키고, B-2번 노드는 A-3번 노드와 연결됨을 저장한다.

전체 코드는 다음과 같다.

import sys
input = sys.stdin.readline

n = 3
m = 3

def dfs(x):
    for i in range(len(a[x])):
        t = a[x][i]
        if visited[t]:
            continue
        visited[t] = True
        # 여기서 b[t]와 이미 연결되었던 a노드가 다른 b와 재매칭된다.
        if (b[t] == 0 or dfs(b[t])):
        	# b[t]와 이어졌던 a노드는 다른 b노드로 연결되었고, 현재 노드는 b[t]와 연결됨
            b[t] = x
            return True
    return False

a = [0] * n
b = [0] * m

for i in range(n):
    visited = [False] * (m)
    if dfs(i):
        cnt += 1

print(cnt)

전체 과정은 이런 식으로 흘러가며, 충분히 변형될 수 있다.

👨‍🏫 문제 풀이

📄 전체 코드 -1

import sys
input = sys.stdin.readline

t = int(input())

def solve():
    cnt = 0
    for choose in chooses:
        for c in range(choose[0], choose[1] + 1):
            if not visited[c]:
                visited[c] = True
                cnt += 1
                break

    return cnt

for _ in range(t):
    n, m = map(int, input().split())
    chooses = [list(map(int, input().split())) for _ in range(m)]
    chooses.sort(key=lambda x: (x[1], x[0]))
    visited = [False] * (n + 1)
    print(solve())

📄 준비

import sys
input = sys.stdin.readline

t = int(input())

...

for _ in range(t):
    n, m = map(int, input().split())
    chooses = [list(map(int, input().split())) for _ in range(m)]
    chooses.sort(key=lambda x: (x[1], x[0]))
    visited = [False] * (n + 1)
    print(solve())

각각 원하는 책의 범위를 입력 받고, 이미 가져갔는지도 체크할 방문 테이블을 설정한다.

📄 풀이

def solve():
    cnt = 0
    for choose in chooses:
        for c in range(choose[0], choose[1] + 1):
            if not visited[c]:
                visited[c] = True
                cnt += 1
                break

    return cnt

원하는 책을 처음부터 순환하면서 이미 가져간 책인지 확인한다. 가져가지 않았다면 방문처리하고 다음 학생으로 넘어간다.

📄 전체 코드 -1

import sys
input = sys.stdin.readline

t = int(input())


def dfs(x):
    for i in range(len(std[x])):
        t = std[x][i]
        if visited[t]:
            continue
        visited[t] = True
        if (books[t] == 0 or dfs(books[t])):
            books[t] = x
            return True

    return False


for _ in range(t):
    n, m = map(int, input().split())
    books = [0] * (n + 1)
    std = [0]
    cnt = 0

    for _ in range(m):
        start, end = map(int, input().split())
        std.append([i for i in range(start, end + 1)])

    for i in range(1, m + 1):
        visited = [False] * (n + 1)
        if dfs(i):
            cnt += 1

    print(cnt)

📌 총평

그리디도 배우고 이분 탐색도 배울 수 있는 좋은 문제였다.