[백준] 1080. 행렬

문제 링크

[백준] 1080. 행렬

풀이 과정

아이디어는 다음과 같습니다.

1. 사전에 행렬 A의 각 요소가 행렬 B의 매칭되는 그 곳의 요소로 바꼈는지 여부를 boolean 배열에 저장하고, 행렬의 변환은 새로 만든 boolean 배열을 토글시킴으로써 수행한다.
2. 뒤집을 3x3 크기의 부분 행렬의 시작 지점을 행렬 A를 순회하며 정한다.
3. 시작 지점의 원소가 우리가 최종적으로 만들 행렬 B의 원소와 다르다면, 행렬 B와 같아지기 위해 뒤집자.
   • 이 부분에서 당장 현재에서의 최적의 답을 선택하는 그리디 알고리즘 사고가 사용된다. 여기서 말하는 최적의 답은, 시작 지점 한 곳을 뒤집어 행렬 B의 그 곳과 같게 하는 것이다.
4. 위 3번을 통해 뒤집는 연산을 끝까지 수행했을 때, boolean 배열의 모든 원소가 false, 즉 행렬 B와 같다면 행렬 A가 행렬 B로 바뀔수 있으므로 연산 횟수를 출력하고, 하나의 원소라도 true 라면 같아질 수 없기에 -1을 출력한다.

행렬 A에서 행렬 B로 변환하는 과정에서 같은 좌표의 두 원소가 바꼈는지, 그대로인지의 정보를 배열 isChanged 에 저장합니다.

좌표 (0,0) 을 시작으로 바뀐 값을 나타내는 true 가 저장되어 있다면, 3x3 크기 만큼을 뒤집어 줍니다. 위 그림에서, (0,0) 을 기준으로 시작되는 3x3 크기의 부분 행렬을 뒤집게 되면, 우측 그림의 배열로 변환되며, 이후 (0,1) 을 기준으로 한 번 더 뒤집으면 모든 원소가 행렬 B와 같게 되므로, 뒤집는 최소 값은 2가 됩니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static boolean[][] isChanged;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        int[][] A = new int[N][M];
        int[][] B = new int[N][M];
        isChanged = new boolean[N][M];
        int cnt = 0;

        for (int i = 0; i < N; i++) A[i] = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();
        for (int i = 0; i < N; i++) B[i] = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (A[i][j] != B[i][j]) isChanged[i][j] = true;
            }
        }

        if (isSame()) {
            System.out.println(0);
            System.exit(0);
        } else {
            outer:
            for (int i = 0; i <= N - 3; i++) {
                for (int j = 0; j <= M - 3; j++) {
                    if (!isChanged[i][j]) continue;

                    cnt++;
                    for (int k = i; k < i + 3; k++) {
                        for (int l = j; l < j + 3; l++) {
                            isChanged[k][l] = !isChanged[k][l];
                        }
                    }

                    if (isSame()) {
                        System.out.println(cnt);
                        System.exit(0);
                    }
                }
            }

            System.out.println(-1);
        }
    }

    static boolean isSame() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (isChanged[i][j]) return false;
            }
        }

        return true;
    }
}