[백준 - 1960번] 행렬만들기 - Java

문제 링크

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

문제

티어: 골드 2
알고리즘: 그르디, 우선순위 큐

입력

첫째 줄에 n(1 ≤ n ≤ 500)이 주어진다. 다음 줄에는 각 행에 있는 1의 개수가 1행부터 n행까지 차례로 주어진다. 그 다음 줄에는 각 열에 있는 1의 개수가 1열부터 n열까지 차례로 주어진다. 행 또는 열에 있는 1의 개수는 n보다 작거나 같은 음이 아닌 정수이다.

출력

만약 행렬을 구할 수 있으면 첫째 줄에 1을 출력한다. 그리고 n개의 줄에 행렬의 수들을 붙여서 출력한다. 만약 구할 수 없다면 첫째 줄에 -1을 출력한다. 가능한 행렬이 여러 개 존재할 경우에는 그 중 임의의 한 개를 출력하면 된다.

풀이

원래의 행렬을 만들어야 하는게 목표다.

그러면 주어진 정보로 어떻게 행렬을 만들어야 할까?

먼저, 각 행에 있는 1의 개수는 다른 말로 표현하면 열의 개수와도 같다.
그러니까 각 행은 1의 개수만큼 열을 선택해야 한다.

그러면 어떤 열을 선택하는 것이 최선일까?

다음 행이 요구하는 1의 개수를 최대한 만족시키게 하기 위해서는 열을 선택할 수 있는 가능성을 높여줘야 한다.

즉, 열의 남은 1의 개수가 큰 열부터 선택하는 것이 최선인 것이다. (우선순위 큐로 1의 개수가 큰 열부터 poll되게끔 구현해준다.)

예를 들어 입력이 다음과 같을 때
4
2 3 1 1
2 2 2 1

1행은 2개의 열을 선택해야 한다. 열의 남은 1의 개수는 2가 가장 크기 때문에 1열과 2열을 선택한다. (3열을 선택해도 무방함) 그러면 열은 1 1 2 1이 된다.

2행은 3개의 열을 선택해야 한다. 그래서 3열과 1열 2열을 선택한다. 그러면 열은 0 0 1 1이 된다.

3행은 1개의 열을 선택해야 한다. 3열을 선택한다. 0 0 0 1

4행은 1개의 열을 선택해야 한다. 4열을 선택한다. 0 0 0 0

이렇게 최선의 선택을 했을 때 행의 요구를 충족하지 못하거나, 행의 요구를 충족하더라도 모든 열의 남은 1의 개수가 0이 아닌 경우에는 어떻게 해도 원래의 행렬을 만들 수 없기 때문에 -1를 출력한다.

그리디 + 우선순위 큐 풀이의 시간 복잡도는 O(N*NlogN)이다.

소스 코드

import java.io.*;
import java.util.*;

class Info implements Comparable<Info> {
    int j, c;
    Info(int j, int c) {
        this.j = j; //열 번호
        this.c = c; //개수
    }
    
    @Override
    public int compareTo(Info o) {
        if(this.c < o.c) {
            return 1;
        } else if(this.c > o.c) {
            return -1;
        }
        return 0;
    }
}

public class Main {
    static int N;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      int[][] answer = new int[N][N];
      
      StringTokenizer st = new StringTokenizer(br.readLine());
      StringTokenizer st2 = new StringTokenizer(br.readLine());
      
      PriorityQueue<Info> pque = new PriorityQueue<>();
      for(int j=0; j<N; j++) {
          int v = Integer.parseInt(st2.nextToken());
          if(v != 0) {
              pque.add(new Info(j, v));
          }
      }
      boolean isPosible = true;
      for(int i=0; i<N; i++) {
          //i는 행 번호
          ArrayList<Info> list = new ArrayList<>();
          int v = Integer.parseInt(st.nextToken()); //행의 개수
          if(v == 0) {
              continue;
          }
          if(pque.size() < v) {
              isPosible = false;
              break;
          }
          
          for(int k=1; k<=v; k++) {
              Info row = pque.poll();
              answer[i][row.j] = 1;
              row.c -= 1;
              if(row.c != 0) {
                  list.add(row);
              }
          }
          
          for(int k=0; k<list.size(); k++) {
              pque.add(list.get(k));
          }
      }
      
      if(pque.size() != 0) {
          isPosible = false;
      }
      
      if(isPosible) {
          StringBuilder sb = new StringBuilder();
          sb.append(1).append("\n");
          for(int i=0; i<N; i++) {
              for(int j=0; j<N; j++) {
                  sb.append(answer[i][j]);
              }
              sb.append("\n");
          }
          System.out.println(sb.toString().trim());
      } else {
          System.out.println(-1);
      }
  }
}