[백준/BOJ C++] 14433번 : 한조 대기 중 / 15271번 : 친구 팰린드롬 2 (이분 매칭)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 14433번 : '한조 대기 중', 15271번 : '친구 팰린드롬 2' 문제의 풀이 코드와 해설에 대해서 다룹니다.

 

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

 

 

14433번 : 한조 대기 중

14433번: 한조 대기 중

 

트롤픽을 원하는 팀원의 번호와 트롤픽의 번호가 주어지고, 트롤픽을 많이 한 쪽이 지게 된다고 하였을 때 승급 가능 여부를 출력하는 문제입니다.

아군의 트롤 픽의 수(= 최대 트롤 픽 매칭 수)와 적군의 트롤 픽의 수를 비교하면 되므로, 이분 매칭을 두 번 사용한 뒤 최대 매칭 수를 비교해주면 됩니다.

 

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

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

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, K1, K2;
    cin >> N >> M >> K1 >> K2;

    while(K1--) {
        int from, to;
        cin >> from >> to;
        Adj[from].push_back(to);
    }

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

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

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

    if(match1 < match2) cout << "네 다음 힐딱이";
    else cout << "그만 알아보자";
}

 

중간에 Adj 벡터를 초기화해주는 것 빼고는 단순 이분 매칭 알고리즘의 2번 반복을 수행해주면 됩니다.

 

 

 

풀이를 제출하면 0ms에 가까운 시간에 통과가 가능합니다.

 

 

15271번 : 친구 팰린드롬 2

15271번: 친구 팰린드롬 2

 

문제가 복잡해보이지만 막상 분석해보면 아주 간단한 문제입니다.

친구 관계 중에서 이성(번호가 각각 짝수, 홀수인 순서쌍) 관계인 경우만 춤을 출 수 있을 때, 최대로 춤을 출 수 있는 학생의 수를 구하는 문제입니다.

남학생과 여학생 사이의 이분 매칭을 수행해서 최대 매칭 수를 이용해주면 되는 문제입니다.

 

다만 매칭의 중복을 방지하기 위해, 여학생이 남학생을 일방적으로 매칭하는 방식으로 구현했습니다.

즉, 친구 관계인 순서쌍 중에서 번호를 2로 나눈 나머지가 1인 번호에서 번호를 2로 나눈 나머지가 0인 번호를 가리키도록 구현하였습니다. (그렇지 않은 경우는 continue로 넘어감)

 

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

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

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;

    while(M--) {
        int from, to;
        cin >> from >> to;
        if(from%2 == 0 && to%2 == 0) continue;
        if(from%2 == 1 && to%2 == 1) continue;
        if(from%2 == 0 && to%2 == 1) swap(from, to);
        Adj[from].push_back(to);
    }

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

    if(match*2 < N) cout << match*2+1;
    else cout << match*2;
}

 

 

 

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