boj1080 행렬_java

문제

0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.

행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0)

입력

첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.

나의 풀이

• 3x3행렬 단위로 변경하고, 그 횟수를 세서 가장 최소값인 경우를 출력하는 문제이다.
• 처음부터 모든 경우를 다 따져서 계산을 해도 2초는 안나올것 같아서 방법을 그렇게 했다.
• 다만, 입력부분에서 3이상이라는 말이 없으므로, 해당부분 예외처리 필요하다.
• 문제 해결
  1. 첫번째 문제는 문제를 잘못 이해하고 있었다. 다른 부분 하나를 뒤집는게 아니라, 그냥 3x3 행렬 내 모든 값을 다 뒤집는 것이었음
  2. 두번째 문제는 (60%에서 fail이 떴음) 3x3 행렬보다 작으면 연산이 안되는 것이지, A,B 두행렬값이 같아 연산이 필요없는 경우도 있기 때문에 무조건 -1 처리하면 안된다는 것
• 핵심 코드

  if(N>=3 && M>=3) {
              for (int t = 0; t < N-2; t++) {
                  for (int k = 0; k < M-2; k++) {
                      if (matrix1[t][k] != matrix2[t][k]) {
                          for (int i = t; i < t + 3; i++) {
                              for (int j = k; j < k + 3; j++) {
                                  if(matrix1[i][j]) matrix1[i][j] = false;
                                  else matrix1[i][j] = true;
                              }
                          }
                          answer +=1;
                      }
                  }
              }
          }

• 전체 코드

  
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.Arrays;
  import java.util.StringTokenizer;
  
  public class boj1080 {
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(br.readLine());
  
          int answer = 0;
          int N = Integer.parseInt(st.nextToken());
          int M = Integer.parseInt(st.nextToken());
  
          boolean[][] matrix2 = new boolean[N][M];
          boolean[][] matrix1 = new boolean[N][M];
  
          for (int i = 0; i < N; i++) {
              String[] temp = br.readLine().split("");
              for (int j = 0; j < M; j++) {
                  if (temp[j].equals("1")) matrix1[i][j] = true;
              }
          }
          for (int i = 0; i < N; i++) {
              String[] temp = br.readLine().split("");
              for (int j = 0; j < M; j++) {
                  if (temp[j].equals("1")) matrix2[i][j] = true;
              }
          }
  
          if(N>=3 && M>=3) {
              for (int t = 0; t < N-2; t++) {
                  for (int k = 0; k < M-2; k++) {
                      if (matrix1[t][k] != matrix2[t][k]) {
                          for (int i = t; i < t + 3; i++) {
                              for (int j = k; j < k + 3; j++) {
                                  if(matrix1[i][j]) matrix1[i][j] = false;
                                  else matrix1[i][j] = true;
                              }
                          }
                          answer +=1;
                      }
                  }
              }
          }
          for (int i = 0; i < N; i++) {
              for (int j = 0; j < M; j++) {
                  if(matrix1[i][j] != matrix2[i][j]){
                      answer = -1;
                  }
              }
          }
          System.out.println(answer);
  
      }
  }

결과