[백준/BOJ C++] 1031번 : 스타 대결 (Diamond V, 최대 유량 알고리즘)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 1031번 : '스타 대결' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Diamond V에 해당하며, 문제를 풀이하기 위해 최대 유량 알고리즘(Network Flow)에 대한 이해가 필요합니다.

 

 

1031번 : 스타 대결

1031번: 스타 대결

 

문제가 긴데, 쉽게 바꿔서 풀이하면 각 행의 합과 각 열의 합이 주어졌을 때 각 칸을 1 또는 0으로 결정하여 행과 열의 합을 맞추는 행렬을 출력하는 문제입니다.

사실 여기까지는 일반적인 최대 유량 알고리즘으로 간단하게 풀리기 때문에 난이도를 높게 잡아도 Platinum 상위 티어인데, 문제는 사전 순으로 가장 앞서는 대진표를 출력해야하기 때문에 이 부분에서 추가적인 알고리즘의 활용이 필요합니다.

 

가장 간단하게 생각해볼 수 있는 풀이는 Edge를 추가하는 과정에서 번호가 높은 것부터 push back 해주는 것인데, 최대 유량 알고리즘은 이렇게 한다고 해서 사전 순으로 가장 앞서는 행렬을 출력하지 못합니다.

따라서 강제적으로 Flow 값을 수정해주는 조치가 필요합니다.

 

 

노드 사이의 연결 자체는 Sour에서부터는 각 행에 각 행의 합에 대응되는 Capacity를, 각 열에서는 각 열의 합에 대응되는 Capacity를 Sink로 연결하고, 모든 행 노드와 모든 열 노드 사이를 Capacity = 1로 연결합니다.

그리고 Network Flow로 가능한 경로를 하나 찾습니다.

 

이제 사전순으로 가장 작은 행렬을 출력하기 위해 Flow를 수정해주어야 합니다.

i행 j열의 Flow = 1인 경우 이 Flow를 0으로 만들고 더 뒷번호 노드들만으로 가능한 다른 경우의 수를 찾아 Flow를 수정해줍니다.

아래의 코드로 확인해보면 더 이해가 쉬울 것입니다.

 

 

#include <bits/stdc++.h>
#define MAX 105
#define INF 1e9
using namespace std;

vector<int> Line[MAX];
int Capacity[MAX][MAX], Flow[MAX][MAX];

void AddEdge(int From, int To, int Amount) {
    Line[From].push_back(To), Line[To].push_back(From);
    Capacity[From][To] = Amount;
}

int MaxFlow(int Sour, int Sink) {
    int FlowSum = 0;
    while(true) {
        int Parent[MAX]; fill(Parent, Parent+MAX, -1);
        queue<int> Queue; Queue.push(Sour);

        while(!Queue.empty() && Parent[Sink] == -1) {
            int Curr = Queue.front(); Queue.pop();
            for(int i=0; i<Line[Curr].size(); i++) {
                int Next = Line[Curr][i];
                if(Capacity[Curr][Next] - Flow[Curr][Next] > 0 && Parent[Next] == -1) {
                    Queue.push(Next);
                    Parent[Next] = Curr;
                }
            }
        }
        if(Parent[Sink] == -1) break;

        for(int i=Sink; i!=Sour; i=Parent[i])
            Flow[Parent[i]][i]++, Flow[i][Parent[i]]--;
        FlowSum++;
    }
    return FlowSum;
}

void ChangeFlow(int Sour, int Sink) {
    int Parent[MAX]; fill(Parent, Parent+MAX, -1);
    queue<int> Queue; Queue.push(Sour);

    while(!Queue.empty() && Parent[Sink] == -1) {
        int Curr = Queue.front(); Queue.pop();
        for(int i=0; i<Line[Curr].size(); i++) {
            int Next = Line[Curr][i];
            if(Curr < Sour || (Curr == Sour && Next < Sink)) continue;
            if(Capacity[Curr][Next] - Flow[Curr][Next] > 0 && Parent[Next] == -1) {
                Queue.push(Next);
                Parent[Next] = Curr;
            }
        }
    }
    if(Parent[Sink] == -1) return;

    Flow[Sour][Sink] = Flow[Sink][Sour] = 0;
    for(int i=Sink; i!=Sour; i=Parent[i])
        Flow[Parent[i]][i]++, Flow[i][Parent[i]]--;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int N, M, Amount, FlowSum = 0, Sour = 101, Sink = 102;
    cin >> N >> M;
    for(int i=1; i<=N; i++) {
        cin >> Amount;
        AddEdge(Sour, i, Amount);
    }
    for(int i=1; i<=M; i++) {
        cin >> Amount;
        FlowSum += Amount;
        AddEdge(50+i, Sink, Amount);
    }
    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++) AddEdge(i, 50+j, 1);

    if(MaxFlow(Sour, Sink) != FlowSum) {
        cout << "-1";
        return 0;
    }

    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++) {
            if(Flow[i][50+j] != 1) continue;
            ChangeFlow(i, 50+j);
        }

    for(int i=1; i<=N; i++) {
        for(int j=1; j<=M; j++) cout << Flow[i][50+j];
        cout << "\n";
    }
}

 

Flow를 수정하는 알고리즘은 ChangeFlow 함수에 구현되어 있습니다.

i번 노드에서 50+j번 노드로 직통하는 유량을 삭제하고 번호가 더 높은 노드들만을 방문하여 도달할 수 있는 다른 루트가 존재하는 경우 Flow를 발견한 루트대로 수정해줍니다.

 

 

 

제출해보면 정답 처리를 받은 것을 확인할 수 있습니다.

문제의 정답률이 약 19%로 매우 낮은데, 이는 문제의 번호가 1031번으로 1페이지에 노출되어있기 때문에 문제의 난이도를 잘 모르고 푼 사람들이 많아서 그런 것으로 예상됩니다.