[백준/BOJ C++] 1298번 : 노트북의 주인을 찾아서 / 11375번 : 열혈강호 (이분 매칭)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 1298번 : '노트북의 주인을 찾아서', 11375번 : '열혈강호' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Platinum 티어에 해당하며, 문제를 풀이하기 위해 이분 매칭 알고리즘에 대한 이해가 필요합니다.

 

[C++ 알고리즘] 이분 매칭 (Bipartite Matching) (BOJ 2188번 : 축사 매칭)

↑ 이분 매칭 알고리즘의 원리, 설명과 이를 활용한 예제의 풀이와 관련된 내용이 위의 포스트에 정리되어 있으니 참고하면 좋습니다.

 

 

1298번 : 노트북의 주인을 찾아서

1298번: 노트북의 주인을 찾아서

 

학생들이 생각하는 노트북의 후보들이 주어질 때, 학생과 그 학생이 생각하는 자신의 노트북 사이의 연결이 최대한 많이 이루어지도록 할 때의 연결 수를 구하는 문제입니다.

이는 전형적인 이분 매칭 문제이기 때문에, 이분 매칭 알고리즘을 사용해서 간단하게 해결할 수 있습니다.

 

↓ 풀이 코드는 아래의 접은 글에 정리되어 있습니다.

#include <bits/stdc++.h>
using namespace std;
const int MAX = 5005;

int Left[MAX], Right[MAX];
vector<int> Adj[MAX];
bool Visit[MAX];

bool DFS(int from) {
    Visit[from] = true;
    for(int i=0; i<Adj[from].size(); i++) {
        int to = Adj[from][i];
        if(Right[to] == -1 || (!Visit[Right[to]] && DFS(Right[to]))) {
            Left[from] = to, Right[to] = from;
            return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;
    for(int i=0; i<M; i++) {
        int from, to; cin >> from >> to;
        Adj[from].push_back(to);
    }

    int match = 0;
    fill(&Left[1], &Left[MAX], -1), fill(&Right[1], &Right[MAX], -1);
    for(int i=1; i<=N; i++)
        if(Left[i] == -1) {
            fill(&Visit[1], &Visit[MAX], false);
            if(DFS(i)) match++;
        }
    cout << match;
}

 

다만 문제에서 Left와 Right의 값들을 -1로 채우는 과정에서 딱 N이나 M만큼의 분량만 채우려고 하면 오답이 발생하므로, 넉넉한 범위를 -1로 fill 해줄 수 있도록 구현하는 편이 좋습니다.

 

메모리 사용은 물론 효율적으로 할수록 좋겠지만, 이런 알고리즘 문제를 풀이할 때에는 기본적인 메모리에 대한 지식만 있다면 나머지는 빠르게 짜는 것에 초점을 두고 풀이하기 위해 넉넉하게 메모리 공간을 잡아주는 편이 낫습니다.

 

 

 

풀이를 제출하면 위와 같이 통과할 수 있습니다.

 

 

11375번 : 열혈강호

11375번: 열혈강호

 

이전에 Network Flow로 해결하려고 했지만 이분 매칭으로 해결하기에 더 적절한 문제이기에 남겨두었던 문제입니다.

역시 이분 매칭을 활용하여 간단하게 해결할 수 있습니다.

 

↓ 풀이 코드는 아래의 접은 글에 정리되어 있습니다.

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1005;

int Left[MAX], Right[MAX];
vector<int> Adj[MAX];
bool Visit[MAX];

bool DFS(int from) {
    Visit[from] = true;
    for(int i=0; i<Adj[from].size(); i++) {
        int to = Adj[from][i];
        if(Right[to] == -1 || (!Visit[Right[to]] && DFS(Right[to]))) {
            Left[from] = to, Right[to] = from;
            return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;
    for(int from=1; from<=N; from++) {
        int S; cin >> S;
        while(S--) {
            int to; cin >> to;
            Adj[from].push_back(to);
        }
    }

    int match = 0;
    fill(&Left[1], &Left[MAX], -1), fill(&Right[1], &Right[MAX], -1);
    for(int i=1; i<=N; i++)
        if(Left[i] == -1) {
            fill(&Visit[1], &Visit[MAX], false);
            if(DFS(i)) match++;
        }
    cout << match;
}

 

코드 자체는 위의 문제와 거의 다른 점이 없습니다.

다만 입력이 무작위로 주어지는 것이 아니고 각 줄 순서대로 해당 번호 직원이 할 수 있는 일의 번호들이 주어지기 때문에 적절히 입력을 처리하여 Adj 벡터에 push_back 해주면 됩니다.

 

 

 

제출해보면 위와 같이 정답 처리를 받을 수 있습니다.