[백준 1960번] [그리디] 행렬만들기

Approach

이 문제를 물론 네트워크 플로우를 활용해서 풀 수는 있는데, 그리디를 활용한 방법으로 접근해보자.

 

문제를 정확히 이해해보면, reordering 성질을 만족하는 것을 쉽게 파악할 수 있다.

예를 들어 다음과 같은 행렬이 있다고 하자.

$$\begin{pmatrix} 1 &1 & 0 & 1 \\ 1 &0 &1 &1 \\ 1 &1 &1 &1 \\ 1&1 &1 &1 \end{pmatrix}$$

 

행과 열의 합을 유지한 상태로 1로 표시된 2개의 element의 위치를 변경할 수 있다.

예를 들어, 첫번째 row vector의 2번째 element대신 3번째 element를 1로 만든 뒤

두번째 row vector의 2번째 element를 1로 만들고 3번째 element를 0으로 만든다.

 

즉, 첫번째 row vector에서는 2번째 element가, 두번째 row vector에서는 3번쨰 element가 선택되었다고 생각해보면

스위칭해서 각각 3번쨰 element와 2번째 element가 선택되었다고 생각해도 일반성을 잃지 않는다.

 

따라서 행 단위로 쭉 내려가면서, 선택할 수 있는 열을 골라주면 된다. (switch 가능하므로 순서는 중요하지 않다.)

다만, 남은 element가 남은 것을 최우선적으로 뽑아주어야 한다.(switch가 불가능한 경우가 존재하므로)

 

해당하는 예시는 다음과 같다.

Row 3 2 2 0

Col 2 2 1 2

Code

#include <bits/stdc++.h>
using namespace std;

int main(void){
    int n;
    cin >> n;
    vector<int> r(n);
    vector<pair<int, int> > c(n);
    int result[n][n];
    memset(result, 0, sizeof(result));
    
    int r_sum = 0;
    int c_sum = 0;
    
    for(int i = 0; i < n; i++){
        cin >> r[i];
        r_sum += r[i];
    }
    
    for(int i = 0; i < n; i++){
        cin >> c[i].first;
        c[i].second = i;
        c_sum += c[i].first;
    }
    
    if(r_sum != c_sum){
        cout << -1 << "\n";
        return 0;
    }
    
    for(int i = 0; i < n; i++){
        int check = r[i];
        sort(c.begin(), c.end(), greater<pair<int, int> >());
        for(int j = 0; j < n; j++){
            if(check == 0) break;
            if(c[j].first > 0){
                check--;
                c[j].first--;
                result[i][c[j].second] = 1;
            }
        }
        if(check > 0){
            cout << -1 << "\n";
            return 0;
        }
    }
    
    cout << 1 << "\n";
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cout << result[i][j];
        }
        cout << "\n";
    }
    return 0;
}

실제로 이렇게 풀면, 네트워크 플로우로 풀었을 때보다 시간/공간 복잡도 측면에서 매우 유리하다