[백준 - 9718번] Matrix Transformation - Java

문제 링크

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

문제

티어: 골드 1
알고리즘: 수학, 그리디, 애드 혹

입력

첫 번째 입력 줄에는 양의 정수 n이 주어지며, 이는 테스트 케이스(행렬)의 개수를 나타냅니다. 각 행렬은 한 줄에 R(2 ≤ R ≤ 30)과 C(2 ≤ C ≤ 30)가 공백으로 구분되어 주어지며, 그 다음 R개의 줄에 각 행이 C개의 정수를 포함합니다. 각 정수는 -20 이상 +20 이하입니다. 각 입력 행렬에는 적어도 하나의 0이 아닌 값이 포함되어 있다고 가정할 수 있습니다.

출력

각 테스트 케이스에 대해 행렬을 0으로 만들 수 있으면 "YES"를, 불가능하면 "NO"를 출력합니다. (모든 출력은 대문자로 작성합니다.)

풀이

제로 행렬로 변환할 수 있는 여부를 판단해 출력해야 한다.

1행 1열에 있는 항목을 0으로 만들어 주려면 인접한 오른쪽이나 아래를 선택해야 한다.

이 두 가지 선택지 중에서 최선의 선택은 없다. 어떤 걸 선택해도 상관없다.

왜냐하면 오른쪽을 선택하나 아래쪽을 선택하나 0으로 만들어 주기 위한 값이 그 항목에 더해질것이며 모든 항목은 결국 인접해 있기 때문이다. (전체를 0으로 만들어 주는 과정에서 결국 마지막 항목으로 몰릴 수밖에 없음)

그래서 0으로 만들어 주기 위한 값을 오른쪽에 더해주고, 이를 마지막 항목 전까지 반복했다. (가장 오른쪽에 있는 항목은 아래를 선택함)

그리고 이미 지나온 항목은 선택지에서 제외해야 한다. 이미 0이기 때문에 현재 항목을 0으로 만들기 위해서 값을 변경한다면 결국 그와 인접한 값이 변하게 되기 때문에 결국 의미없는 계산을 더 할 뿐이다.

마지막으로 [r-1][c-1]이 0인지 아닌지 체크한다.
0이면 제로 행렬이 가능하고,
0이 아니면 제로 행렬이 불가능한 경우가 된다.

이 풀이의 시간 복잡도는 O(n r c)다.

소스 코드

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

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());
      StringBuilder sb = new StringBuilder();
      for(int t=1; t<=n; t++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          int r = Integer.parseInt(st.nextToken());
          int c = Integer.parseInt(st.nextToken());
          
          int[][] matrix = new int[r][c];
          
          for(int i=0; i<r; i++) {
              StringTokenizer st2 = new StringTokenizer(br.readLine());
              for(int j=0; j<c; j++) {
                  matrix[i][j] = Integer.parseInt(st2.nextToken());
              }
          }
          
          sb.append(answer(r, c, matrix)).append("\n");
      }
      System.out.println(sb.toString().trim());
  }
  
  static String answer(int r, int c, int[][] matrix) {
      String result = "YES";
      
      for(int i=0; i<r; i++) {
          for(int j=0; j<c; j++) {
              if(i == r - 1 && j == c - 1) {
                  break;
              }
              int v = -1 * matrix[i][j];
              if(j == c - 1) {
                  matrix[i + 1][j] += v;
              } else {
                  matrix[i][j + 1] += v;
              }
          }
      }
      
      if(matrix[r - 1][c - 1] != 0) {
          result = "NO";
      }
      return result;
  }
}