[BOJ / C++] 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)

출력

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

Solved.ac 레벨

골드 II

풀이

처음으로 풀어 본 이분 매칭 (Bipartite Matching) 알고리즘 문제다. 이분 그래프에 대해서 공부하려고 찾다가 영상을 잘못 봐서 그렇긴 한데... 아무튼 재미가 있는 알고리즘이었다.

내가 참고한 자료는 동빈나님의 영상이었다. 

이분 매칭은 말 그대로 두 개의 집합을 1 : 1로 매칭해주는 것을 뜻한다. DFS를 통해 구현할 수 있으며, 각 집합에서 어떠한 요소가 점유하고 있는 다른 집합의 요소를 판별해내며 매칭을 수행한다.

 

int형 bookNode 배열은 특정 책을 점유한 학생의 정보를 저장하며, bool형 visited 배열을 통해 이미 나눠준 책을 관리한다.

자세한 풀이 과정은 코드에 주석으로 달아두도록 하겠다.

풀이

#include<bits/stdc++.h>

#define MAX 20001

using namespace std;

int t;
vector<pair<int, int>> arr; //a ~ b 사이 책
int bookNode[1001]; //책 점유한 학생 정보
bool visited[1001];

// 매칭에 성공한 경우 t, 실패 false
bool DFS(int x) {
    //연결된 모든 노드에 대해서 들어갈 수 있는지
    for (int i = arr[x].first; i <= arr[x].second; i++) {

        //이미 처리한 노드는 더 이상 볼 필요 X
        if (visited[i]) continue;
        visited[i] = true;

        //비어있거나 점유 노드에 더 들어갈 공간이 있는 경우
        if (bookNode[i] == -1 || DFS(bookNode[i])) {
        	//해당 학생에게 책을 점유 처리 후 매칭 성공 리턴.
            bookNode[i] = x;
            return true;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> t;

    while(t--) {
        int n, m, ans = 0;
        cin >> n >> m;

        arr.clear();
        for(int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            arr.push_back({a, b});
        }
		
        //bookNode에는 점유한 학생 정보를 저장할 것이다.
        memset(bookNode, -1, sizeof(bookNode));

        for(int i = 0; i < m; i++) {
            memset(visited, false, sizeof(visited));
            if(DFS(i)) ans++;
        }

        cout << ans << "\n";
    }



    return 0;
}

9576번: 책 나눠주기