백준 1867번: 돌멩이 제거 (C++)

접근

https://www.acmicpc.net/problem/1867

1867번: 돌멩이 제거

각 줄의 돌의 수를 찾아 가장 많은 돌을 가진 줄부터 삭제하는 방향의 그리디 알고리즘으로 먼저 풀어보았다가 예상대로 틀렸다.

푸는 방향을 못찾아 다른 분의 풀이를 참고하였고, 네트워크 플로우의 한 종류인 최대 이분 매칭 알고리즘을 이용하여 푼다는 것을 확인했다. 알고리즘에 대한 이해는 아래 글을 참고하였다.

https://cocoon1787.tistory.com/819

[C++] 백준 1867번 - 돌멩이 제거

코드

#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

#define endl '\n'
#define MAX_N 501

int N, K, ans;
int visited[MAX_N];
int bm[MAX_N];
vector<vector<int>> grid(501);

int dfs(int row) {
    if (visited[row]) return 0;
    visited[row] = 1;
    for (int col : grid[row]) {
        if (bm[col] == 0 || dfs(bm[col])) {
            bm[col] = row;
            return 1;
        }
    }
    return 0;
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> K;
    int a, b;
    for (int i = 0; i < K; i++) {
        cin >> a >> b;
        grid[a].push_back(b);
    }
    for (int i = 1; i <= N; i++) {
        memset(visited, 0, sizeof(visited));
        if (dfs(i)) ans++;
    }

    cout << ans << endl;

    return 0;
}

더 생각해 볼 것?

네트워크 플로우 알고리즘에 대한 공부가 필요할 것 같다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!