[C/C++] 백준 - 1298 노트북의 주인을 찾아서

www.acmicpc.net/problem/1298

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

- 접근법

각 노드들이 선호하는 방번호가 있고 최대한 많은 노드들을 각기 다른 방에 1개씩 넣는 법을 묻는 문제이다.

즉, 단순한 이분매칭으로 해결할 수 있다. 문제에서 주어진 노드들의 개수(N)도 100으로 여유있고 간선들의 개수(5000)도 여유있으므로 단순하고 빠른 DFS로 해결할 수 있다.

 

로직은 간단히 말하면, 탐색하는 노드가 선호하는 방 번호에 '비어'있다면 바로 매칭시켜주고 누가 점거하고 있다면, 그 점거하고 있던 노드가 다른 방으로 양보해줄 수 있는 지 탐색하고 가능하면 점거하고 있던 노드를 다른 방으로 빼고 원래 노드를 넣어준다. 이를 전체 노드 별로 반복하면 매칭이 완료된다.

---

- 유사문제www.acmicpc.net/problem/2188

2188번: 축사 배정

1298 문제를 확실히 이해하고 풀었다면 이 문제에 도전하는 것도 좋을 것 같다.

 

---

- 소스코드

 

#include<iostream>
#include<vector>
using namespace std;
int N, M;
vector<int> edge[102];
int matched[102];
bool visit[102];
bool DFS(int vertex) {
    for (int i = 0; i < edge[vertex].size(); i++) {
        int want_vertex = edge[vertex][i];
        if (visit[want_vertex]) continue;
        visit[want_vertex] = true;
        if (matched[want_vertex] == 0) {
            matched[want_vertex] = vertex;
            return true;
        }
        else {
            int move_vertex = matched[want_vertex];
            if (DFS(move_vertex)) {
                matched[want_vertex] = vertex;
                return true;
            }
        }
    }
    return false;
}
void init() {
    for (int i = 0; i <= N; i++) visit[i] = false;
}
int solution() {
    int answer = 0;
    for (int i = 1; i <= N; i++) {
        init();
        if (DFS(i)) answer++;
    }
    return answer;
}
int main() {
    int a, b;
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        edge[a].push_back(b);
    }
    cout<<solution();
    return 0;
}