1080번: 행렬

문제

0과 1로 이루어진 N×M 크기의 행렬 A와 B가 있습니다. 행렬 A를 행렬 B로 바꾸기 위해 3×3 크기의 부분 행렬에 있는 모든 원소를 뒤집는 연산(0을 1로, 1로 0으로)을 사용할 수 있습니다. 행렬 A를 행렬 B로 바꾸는 데 필요한 연산 횟수의 최솟값을 구하는 프로그램을 작성하는 문제입니다.

• 입력: 첫째 줄에 N과 M이 주어집니다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 행렬 A가, 그 다음 N개의 줄에 행렬 B가 주어집니다.
• 출력: 첫째 줄에 문제의 정답을 출력합니다. 만약 A를 B로 바꿀 수 없다면 -1을 출력합니다.

링크: https://www.acmicpc.net/problem/1080

풀이: 탐욕법(Greedy)을 활용한 3x3 부분 행렬 뒤집기

이 문제는 왼쪽 위에서부터 순차적으로 탐색하며, 두 행렬의 원소가 다를 때 무조건 3x3 영역을 뒤집는 탐욕법(Greedy) 방식으로 해결할 수 있습니다. 특정 좌표 (i, j)의 값을 바꿀 수 있는 3x3 연산은 (i, j)를 좌측 상단으로 하는 연산이 마지막이므로, 해당 위치의 값이 서로 다르다면 반드시 그 시점에 뒤집어야만 전체를 똑같이 맞출 수 있습니다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       StringTokenizer st = new StringTokenizer(br.readLine());
       int n = Integer.parseInt(st.nextToken());
       int m = Integer.parseInt(st.nextToken());

       char[][] a = new char[n][m];
       for (int i = 0; i < n; i++) {
          a[i] = br.readLine().toCharArray();
       }

       char[][] b = new char[n][m];
       for (int i = 0; i < n; i++) {
          b[i] = br.readLine().toCharArray();
       }

       int ans = 0;
       for (int i = 0; i < n - 2; i++) {
          for (int j = 0; j < m - 2; j++) {
             // A와 B의 현재 위치 값이 다르다면 B 배열의 3x3 영역 뒤집기
             if (a[i][j] != b[i][j]) {
                for (int k = 0; k < 3; k++) {
                   for (int l = 0; l < 3; l++) {
                      if (b[i + k][j + l] == '0')
                         b[i + k][j + l] = '1';
                      else
                         b[i + k][j + l] = '0';
                   }
                }
                ans++;
             }
          }
       }

       // 모든 연산이 끝난 후 두 행렬이 완전히 일치하는지 최종 검사
       for (int i = 0; i < n; i++) {
          for (int j = 0; j < m; j++) {
             if (a[i][j] != b[i][j]) {
                bw.write("-1");
                bw.flush();
                return;
             }
          }
       }

       bw.write(ans + "");

       bw.flush();
    }
}

알고리즘 분류

그리디 알고리즘 (Greedy)