[백준/BOJ] 12843번 : 복수전공 (이분 매칭, Platinum III)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 12843번 : '복수전공' 문제의 풀이 코드를 다루고 있습니다.

 

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

 

 

12843번 : 복수전공

12843번: 복수전공

 

컴퓨터공학부 수업과 소프트웨어 학부의 겹치는 수업들을 빼고 수업을 듣는다고 할 때 수강할 수 있는 최대한 많은 수업의 수를 구하는 문제입니다.

 

 

 

우선 수업의 그룹을 c와 s로 나눌 수 있으므로, 이분 매칭으로 접근이 가능한 문제입니다.

겹치는 내용들을 간선으로 연결하고 생각해보면, 매칭이 된 두 수업 중에서는 하나만 들을 수 있습니다.

따라서 최대 매칭 간선을 구하고, 이들을 N에서 빼주면 들을 수 있는 수업의 수를 얻을 수 있습니다.

 

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

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

vector<int> Adj[MAX];
int Left[MAX], Right[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;
    vector<int> cList, sList;

    for(int i=0; i<N; i++) {
        int val; char c;
        cin >> val; cin.clear(); cin >> c;
        if(c == 'c') cList.push_back(val);
        else sList.push_back(val);
    }

    for(int i=0; i<M; i++) {
        int val1, val2; cin >> val1 >> val2;
        for(int i=0; i<cList.size(); i++)
            if(cList[i] == val1) Adj[val1].push_back(val2);
        for(int i=0; i<sList.size(); i++)
            if(sList[i] == val1) Adj[val2].push_back(val1);
    }

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

    cout << N - match;
}

 

까다로운 부분은 넘버링인데, 저의 경우에는 벡터에 cList와 sList를 따로 선언하여 번호들을 저장하였습니다.

저장 과정은 val1와 val2가 선언되어있는 for문에 정리되어 있으니 코드를 참고하시면 됩니다.

 

 

 

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