[백준/BOJ] 17481번 : 최애 정하기 / 1574번 : 룩 어택 (이분 매칭)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 17481번 : '최애 정하기', 1574번 : '룩 어택' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

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

 

 

17481번 : 최애 정하기

17481번: 최애 정하기

 

N명의 친구들이 M명의 멤버들 중에 좋아하는 멤버들이 있을 때 최애 멤버를 겹치지 않도록 최대 매칭을 시켜주는 문제입니다.

N명의 친구들이 모두 겹치지 않게 최애 멤버를 매칭시킬 수 있으면 YES를 출력하고, 아닐 경우에는 최대 매칭 수가 몇이었는지를 출력해주면 됩니다.

 

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

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

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;

    map<string, int> member;
    for(int i=1; i<=M; i++) {
        string name; cin >> name;
        member[name] = i;
    }
    for(int i=1; i<=N; i++) {
        int S; cin >> S;
        while(S--) {
            string name; cin >> name;
            Adj[i].push_back(member[name]);
        }
    }

    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 == N) cout << "YES";
    else cout << "NO\n" << match;
}

 

다만 이 문제의 경우에는 멤버들의 이름이 문자열로 주어지기 때문에, 해시맵을 사용하여 각 문자열에 대응되는 번호를 만들어주어야 해결하기에 수월합니다.

 

 

 

위의 풀이대로 코드를 작성하여 제출하면 시간이 꽤 소모되긴 하지만 넉넉한 소요 시간으로 통과할 수 있습니다.

 

 

1574번 : 룩 어택

1574번: 룩 어택

 

R×C 크기의 체스판에서 N개의 좌표에는 룩을 놓지 못한다고 할 때 룩이 서로 공격할 수 없도록 놓을 수 있는 최대 룩의 수를 구하는 문제입니다.

 

행과 열에 대응되는 노드들을 각각 그룹으로 묶은 뒤, 각 행에서 놓을 수 있는 열들에 대해 노드 사이의 간선을 구성합니다.

그 다음 놓지 못하는 N개의 칸에 대응되는 간선은 다시 지워주고, 이분 매칭을 수행하면 최대로 놓을 수 있는 룩의 수를 알 수 있습니다.

이렇게 구현하면 행과 열 사이가 일대일로 대응이 되므로 같은 행이나 열 사이에 두 개 이상의 룩을 놓을 수 없도록 장치가 마련됩니다.

 

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

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

int R, C, N;
int Adj[MAX][MAX], Left[MAX], Right[MAX];
bool Visit[MAX];

bool DFS(int from) {
    Visit[from] = true;
    for(int i=1; i<=C; i++) {
        if(Adj[from][i] == 0) continue;
        int to = 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);

    cin >> R >> C >> N;
    for(int i=1; i<=R; i++)
        for(int j=1; j<=C; j++) Adj[i][j] = 1;
    while(N--) {
        int x, y; cin >> x >> y;
        Adj[x][y] = 0;
    }

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

    cout << match;
}

 

N개의 좌표에 대해서는 다시 간선을 지워줘야하기 때문에, Adj를 벡터로 사용하기보다는 입력 범위가 작으므로 그냥 2차원 배열로 선언해서 사용하는 편이 훨씬 편합니다.

 

 

 

풀이 코드를 제출하면 위와 같은 기록으로 모든 테스트케이스를 통과할 수 있습니다.