[알고리즘] 이분 매칭(Bipartite Matching)

1. 이분 매칭

네트워크 플로우(Network Flow) 알고리즘에서 두 정점 사이의 용량이 1이고, 정점이 두 집합으로 구분되는 특수한 경우.

한쪽 그룹을 X, 다른 그룹을 Y라고 할 때, X → Y로의 최대 유량을 구하는 문제.

이때, 각 용량이 1이므로 최대 매칭 수를 찾는 문제로 볼 수 있음.

 

---

2. 알고리즘 예시

DFS를 활용하여, 매칭을 하나씩 선택하는 과정을 거친다.

예시는 조금 복잡하지만, 백준 문제의 예시를 가져왔다. 세부적인 예시는 아래와 같다.

 

다음과 같이 왼쪽 그룹, 오른쪽 그룹에 있는 정점에 대하여 각 선분 중 연결되어 있다. DFS를 응용하여 편하게 최적의 답을 찾을 수 있다. 우선 1번점에서 연결할 수 있는 최적의 점을 찾는다.

그러면, 왼쪽 1번점, 오른쪽 2번점을 연결할 수 있다.

이후, 왼쪽 2번점에서 연결할 수 있는 점을 고려한다. 가장 먼저 만나는 오른쪽 2번점은 왼쪽 1번점이 차지하고 있다. 이때, 왼쪽 1번점을 연결할 수 있는 다른 점을 생각하고, 오른쪽 5번점을 연결할 수 있다. 이후 왼쪽 2번점, 오른쪽 2번점을 연결한다.

다음은 왼쪽 3번점을 오른쪽 1번점과 연결한다.

여기서 왼쪽 4번점을 연결할 때, 다음과 같은 순서로 이어진다.

1. 왼쪽 4번 점을 오른쪽 1번 점과 연결하기 위해 지금 오른쪽 1번 점과 연결된 왼쪽 3번 점을 확인

2. 왼쪽 3번 점을 지금 연결된 1번 점이 아닌 5번 점과 연결하기 위해 오른쪽 5번 점과 연결된 왼쪽 1번 점을 확인

3. 왼쪽 1번 점을 다시 오른쪽 2번 점과 연결하기 위해 왼쪽 2번 점을 확인

4. 왼쪽 2번 점을 오른쪽 3번 점과 연결할 수 있음. 그러면 지금까지 확인한 역순으로 점을 다시 연결

그러면 최종적으로 이 형태가 된다.

5번 점을 연결하기 위해 위와 같은 과정을 반복한다 하여도 새로운 연결을 만들어내지 못하므로 최대 매칭값은 4개로 마무리된다.

 

---

3. 문제에 적용

총 세문제의 풀이를 따라가며 문제에 어떻게 적용하는지, 어떻게 더 좋은 풀이를 작성할 수 있는지 보겠다.

문제는 백준 9576 책나눠주기, 백준 2188 축사 배정, 백준 11375 열혈 강호

세 문제 모두 거의 비슷한 풀이로 풀리지만, 어떻게 생각을 쌓아가면 될지 이 글에서 나눌 예정이다.

 

3.1 책 나눠주기

문제 링크 : https://www.acmicpc.net/problem/9576

9576번: 책 나눠주기

문제 풀이 코드 : https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/9000/9576.py

GitHub - mintropy/PS: 다양한 알고리즘 문제 풀이 저장소입니다.

 

이분 매칭과 그리디 방식으로 해결할 수 있다. 이번 글은 이분 매칭과 관련한 글이므로 이분 매칭 풀이 위주로 이어나가겠다. 풀이 코드 일부를 가져오면 다음과 같다.

def dfs(student):
    global students, books
    if visited[student]:
        return False
    visited[student] = True
    a, b = students[student]
    for book in range(a, b + 1):
        if not books[book] or dfs(books[book]):
            books[book] = student
            return True
    return False


if __name__ == "__main__":
    for _ in range(int(input())):
        N, M = MIIS()
        students = [[]] + [list(MIIS()) for _ in range(M)]
        books = [0] * (N + 1)
        for student in range(1, M + 1):
            visited = [False] * (M + 1)
            dfs(student)
        print(N + 1 - books.count(0))

왼쪽 점 집합인 학생, 오른쪽 점 집합인 책을 기준으로 잡는다.

학생을 1번부터 M번까지 순회하며(왼쪽 점 순서대로 탐색), 각 학생이 원하는 책을 dfs함수에서 탐색한다. 책의 입력 순서의 정렬은 중요하지 않고, 각 책마다 가능한지 탐색한다.

처음 이 dfs함수를 구성하는게 잘 이해되지 않았지만, 하나씩 그려가며 풀어보니 조금은 이해할 수 있었다.

 

3.2 축사 배정

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

2188번: 축사 배정

문제 풀이 코드 : https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/2000/2100/2188.py

GitHub - mintropy/PS: 다양한 알고리즘 문제 풀이 저장소입니다.

 

위의 책 나눠주기와 풀이코드가 거의 같지만, 한 가지 차이점은 위의 문제에서는 책의 범위가 주어진 반면, 이 문제에서는 특정 축사로 주어진다. dfs 내부 for문 구성만 잘하면 되는 부분이다.

 

3.3 열혈 강호

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

11375번: 열혈강호

문제 풀이 코드 : https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/11000/11375.py

GitHub - mintropy/PS: 다양한 알고리즘 문제 풀이 저장소입니다.

 

문제는 위의 축사 배정과 완전히 같은데, 점의 개수가 양쪽 200개에서 1,000개로 늘어났다는 차이점이 있다. 그래서 위의 문제까지 사용했던 코드로는 통과할 수 없었다. (정확히는 python은 TLE, pypy로 통과) 그래서 코드를 수정하며 두 가지 변경사항을 적용했다.

 

첫 번째로, 왼쪽, 오른쪽 점 집합을 left, rigth로 사용했다. 보통은 문제 설명에 맞게 변수를 지정하지만, 때로는 풀이의 흐름에 더 가깝게 표현하는것이 문제를 매우 쉽게 바라볼 수 있게 한다. 이분 매칭은 왼쪽, 오른쪽 점을 왔다 갔다 하는 바람에 명확하게 인지하는 것이 아니라서 문제 풀이 과정에서 헷갈렸던 적이 많다. 따라서 더 쉽게 풀기 위해 left, right로 나누어 풀었다.

두 번째로, dfs 내부를 수정했다. 해당부분 코드는 다음과 같다.

def bipartite_matching(l):
    global left, right, visited
    visited[l] = True
    for r in left[l]:
        if not right[r]:
            right[r] = l
            return True
    for r in left[l]:
        if not visited[right[r]] and bipartite_matching(right[r]):
            right[r] = l
            return True
    return False

우선 명시적으로 bipartite_matching으로 함수 이름을 바꾸었다.

그리고 for문을 2개 사용하여 진행했고, 이를 통하여 시간을 매우 줄일 수 있었다. 2개의 for문은 다음과 같은 역할을 한다. 첫 번째 for문은 왼쪽 점에서 매칭 하려는 오른쪽 점이 아직 매칭 되지 않은 경우이다. 두 번째 for문은 연결하고 싶은 오른쪽 점과 매칭 된 왼쪽 점을 아직 확인하지 않았고, 해당 오른쪽 점과 매칭 했을 때 가능한 경우이다.

 

---

4. 생각 정리

예전 최대 유량 문제를 지나가듯이 공부하였고, 잘 기억나지는 않았다. 거의 새로 공부하듯이 기억을 훑어보았고, 조금씩 코드를 맞추어 갈 수 있었다.

특히 세 문제의 풀이가 기본적으로 비슷하지만, dfs 내부 for문을 구성하는 방법이나, 더 많은 점을 효율적으로 탐색하기 위해 2개의 for문을 사용하는 등 조금씩 변화를 적용하여 풀어낼 수 있었다.