접근

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

 

1867번: 돌멩이 제거

첫째 줄에 n과 k가 주어진다. (1 ≤ n ≤ 500, 1 ≤ k ≤ 10,000) 이후 k개의 줄에는 돌멩이의 위치가 한 줄에 하나씩 주어진다. 줄마다 첫 번째 숫자는 행 번호, 두 번째 숫자는 열 번호를 나타낸다. 입

www.acmicpc.net

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

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

https://cocoon1787.tistory.com/819

 

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

📖 문제 📋 코드 #include #include #include using namespace std; int n, k, ans; bool visited[501]; int bm[501]; // Bipartite Matching vector > grid(501); bool DFS(int row) { if (visited[row]) //..

cocoon1787.tistory.com

코드

#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;
}

더 생각해 볼 것?

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

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

반응형
  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기