[백준/BOJ C++] 11376번 : 열혈강호 2 / 1671번 : 상어의 저녁식사 (이분 매칭)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 11376번 : '열혈강호 2', 1671번 : '상어의 저녁식사' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

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

 

 

11376번 : 열혈강호 2

11376번: 열혈강호 2

 

N개의 직원에 대해 M개의 일을 적절히 연결시켜서 할 수 있는 일의 최대 개수를 구하는, 전형적인 이분 매칭 문제들 중 하나입니다.

이전 포스트에서 풀이했던 '열혈강호' 문제와 거의 동일하지만 이 문제에서는 한 명의 직원이 최대 두 개의 일을 수행할 수 있으므로, 간선 연결에 대한 추가적인 조치가 필요합니다.

인상적인 점은, 위의 스크린샷에는 나오지 않았지만 문제 제한 시간이 4초로 상당히 넉넉한 제한 시간을 두고 있다는 점입니다.

 

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

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

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*2-1].push_back(to);
            Adj[from*2].push_back(to);
        }
    }

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

 

기존 이분 매칭 알고리즘은 한 개의 Left group의 노드가 하나의 간선만을 가질 수 있었지만 이 문제에서는 최대 2개의 간선을 가지도록 구현해야하기 때문에, 같은 직원에 대해 2개의 노드를 만들어 각각 1개의 독립된 간선을 가질 수 있도록 구현해주면 됩니다.

2배의 노드들을 관리하기 쉽도록, i번 직원은 2*i-1번 노드와 2*i번 노드에 대응되도록 구현하였습니다.

 

매칭을 수행할 때에도 역시 1번 노드부터 2*N번 노드까지 매칭을 수행하도록 반복문의 범위를 조작해줍니다.

나머지 과정은 기존의 '열혈강호' 문제의 풀이와 같습니다.

 

 

 

풀이를 제출해보면 1240ms의 시간과 적지않은 메모리를 소모하며 정답 처리를 받을 수 있습니다.

 

 

1671번 : 상어의 저녁식사

1671번: 상어의 저녁식사

 

상어의 크기, 속도, 지능이 모두 다른 상어의 크기, 속도, 지능보다 크거나 같다면 상어를 먹을 수 있고 하나의 상어는 다른 상어를 최대 2개까지만 먹을 수 있다고 할 때 살아남을 수 있는 최소 상어 수를 구하는 문제입니다.

 

상어들을 똑같은 2개의 그룹으로 만들어서 상어가 다른 상어를 잡아먹는 경우 왼쪽 그룹의 노드에서 오른쪽 그룹의 노드로 간선을 만들어 체크하는 방식을 통해 이분 매칭으로 해결할 수 있습니다.

 

이 경우 상어의 순서가 반대로 된 경우에도 한 번 더 검사하게 되므로, 뒤집어서 같은 순서쌍에 대해서는 한 번만 검사하게 만들기 위해 i보다 큰 j에 대해서만 이중 for문이 돌아가도록 설계해주면 됩니다.

 

그리고 하나의 상어는 최대 2마리의 상어만을 잡아먹을 수 있음을 코드로 구현하기 위해, 먼저 최대 한 마리까지 잡아먹도록 DFS로 탐색을 해주고 Visit 배열을 초기화 한 뒤 DFS로 한 번 더 탐색하여 아직 Right 배열이 -1인(= 아직 잡아먹히지 않은) 상어들에 대해서 Left 그룹의 상어들이 한 번 더 잡아먹을 수 있는지 체크해주면 됩니다.

 

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

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

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, val[MAX][3]; cin >> N;
    for(int i=1; i<=N; i++) cin >> val[i][0] >> val[i][1] >> val[i][2];

    for(int i=1; i<=N; i++)
        for(int j=i+1; j<=N; j++) {
            if(val[i][0] == val[j][0] && val[i][1] == val[j][1] && val[i][2] == val[j][2])
                Adj[i].push_back(j);
            else if(val[i][0] >= val[j][0] && val[i][1] >= val[j][1] && val[i][2] >= val[j][2])
                Adj[i].push_back(j);
            else if(val[i][0] <= val[j][0] && val[i][1] <= val[j][1] && val[i][2] <= val[j][2])
                Adj[j].push_back(i);
        }

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

 

상어 수는 최대 50이므로 MAX는 55 정도로만 잡아주면 됩니다.

살아남을 수 있는 최소 상어 수를 출력하라고 하였으므로 전체 상어 수에서 잡아먹을 수 있는 match 수를 빼주어 출력해주면 됩니다.

 

 

 

풀이대로 코드를 작성하여 제출하면 위와 같이 모든 테스트케이스에 대해 통과함을 확인할 수 있습니다.