1960 - 행렬만들기

문제 링크

---

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

문제 요약

---

\(N*N\)행렬의 각 열들의 합과 각 행들의 합이 주어졌을 때 원본 행렬을 복구해 출력하는 문제다. 원본 행렬이 가질 수 있는 값은 0또는 1이다. 물론 만들지 못하는 경우도 주어질 수 있으며 이때는 -1을 출력한다.

문제 풀이

---

이 문제는 전형적인 네트워크 플로우로 문제다.(그리디로도 해결이 가능하다고 한다.) 모델링 또한 너무 간단하다.

우선 왼쪽에는 각 행들을 대표할 수 있는 정점들을 두고 오른쪽에는 각 열들을 대표할 수 있는 정점들을 둔다. 그리고 소스와 왼쪽 정점들을, 싱크와 오른쪽 정점들을 연결해준다. 각각의 \(capacity\)는 행들의 합과 열들의 합으로 설정해 준다.

그 뒤 행들을 대표하는 정점들과 열들을 대표하는 정점들이 모두 연결되어 있는 완전 그래프 형태로 만들어 준다. 이 간선들의 \(capacity\)는 1이다. 그 뒤 \(max\ flow\)를 구하면 답을 구할 수 있다.

답을 구하는 과정은 크게 두 가지 파트로 나누어 진다. 

첫 번째 파트는 실제로 원본 행렬을 만들 수 있는지 판단하는 것이다. 이는 주어진 행들의 합의 합과 열들의 합의 합이 같은지 확인한 다음에 \(max\ flow\)또한 이와 같은지 확인해주면 된다.

두 번째 파트는 실제로 원본 행렬을 만드는 과정이다. 이 과정이 조금 까다로울 수 있지만 우리가 모델링한 그래프의 의미를 정확하게 이해하고 있다면 어렵지 않게 행렬을 복원할 수 있다. 만약 첫 번째 행을 대표하는 정점에서 두 번째 열을 대표하는 정점으로 \(flow\)가 1흐른다고 생각을 해보자. 이는 우리가 복원할 행렬의 \((1,\ 2)\)에 1이 채워져 있다는 의미다. 만약 흐르는 유량이 없다면 그 칸은 0으로 채워지면 될 것이다.

소스 코드

---

#include <stdio.h>
#include <queue>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 987654321;
int row, col, n, x, src, sink, N, C[1010][1010], D[1010], iter[1010];

bool bfs() {
  memset(D, -1, sizeof(D));
  queue<int> q;
  D[src] = 0;
  q.push(src);
  
  while (!q.empty()) {
    int here = q.front();
    q.pop();
    
    for (int there = 0 ; there < N ; ++there) {
      if (C[here][there] && D[there] == -1) {
        D[there] = D[here] + 1;
        q.push(there);
      }
    }
  }
  
  return D[sink] != -1;
}

int dfs(int here, int flow) {
  if (here == sink) {
    return flow;
  }
  
  for (int& there = iter[here] ; there < N ; ++there) {
    if (C[here][there] && D[here] < D[there]) {
      int minFlow = dfs(there, min(flow, C[here][there]));
      if (minFlow) {
        C[here][there] -= minFlow;
        C[there][here] += minFlow;
        return minFlow;
      }
    }
  }
  
  return 0;
}

int maxFlow() {
  int ret = 0;
  while (bfs()) {
    int flow;
    memset(iter, 0, sizeof(iter));
    while ((flow = dfs(src, INF))) {
      ret += flow;
    }
  }
  return ret;
}

int main() {
  scanf("%d", &n);
  src = 2 * n;
  sink = 2 * n + 1;
  N = 2 * n + 2;
  
  for (int i = 0 ; i < n ; ++i) {
    scanf("%d", &x);
    C[src][i] += x;
    row += x;
  }
  for (int i = 0 ; i < n ; ++i) {
    scanf("%d", &x);
    C[i + n][sink] += x;
    col += x;
  }
  for (int i = 0 ; i < n ; ++i) {
    for (int j = 0 ; j < n ; ++j) {
      ++C[i][j + n];
    }
  }
  
  int flow =  maxFlow();
  if (row == flow && col == flow) {
    puts("1");
    for (int i = 0 ; i < n ; ++i) {
      for (int j = 0 ; j < n ; ++j) {
        printf("%d", C[i][j + n] ? 0 : 1);
      }
      puts("");
    }
  } else {
    puts("-1");
  }
}