[Baekjoon] 1080번: 행렬

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

1080번: 행렬

문제 설명

행렬 A와 B가 주어진다. 이 행렬은 모두 0 또는 1로 구성되어 있다. A를 B로 변환하는 최소 연산을 구해야 한다. 연산 방법은 0이면 1로, 1이면 0으로 3x3만큼 변환한다.

풀이 방법

간단하게 생각하면 간단하고 어렵게 생각하면 한없이 어려운 게 그리디 문제인 거 같다.

[0, 0] 부터 한 칸씩 이동하면서 해당 칸이 B와 다르다면 해당 위치부터 3x3의 모든 칸을 반전시키면 된다. 그리고 마지막에 A와 B를 비교해서 동일하면 그동안 뒤집었던 카운트를, 다르면 -1을 출력하면 된다.

반전하는 방법으로 XOR 연산자인 ^(carrot)을 사용했다. XOR 연산은 두 비트가 같은 경우 0, 다른 경우 1을 출력하는 비트 연산이다. 예를 들어 0000, 1010 을 XOR 연산하면 1010이라는 결과를 얻게 된다. 1과 XOR 연산을 수행하면 항상 반전된 비트를 얻을 수 있다. 0을 1로, 또는 1을 0으로 뒤집으려면 if 문을 써도 되지만 비트 연산을 활용해서 불필요한 분기를 제거했다.

import java.io.*;

class Main {
    
    static int N, M;
    static int[][] srcMatrix;
    static int[][] dstMatrix;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] split = br.readLine().split(" ");
        N = Integer.parseInt(split[0]);
        M = Integer.parseInt(split[1]);
        
        srcMatrix = new int[N][M];
        dstMatrix = new int[N][M];
        
        // src
        for (int i = 0; i < N; i++) {
            split = br.readLine().split("");
            for (int j = 0; j < M; j++) {
                srcMatrix[i][j] = Integer.parseInt(split[j]);
            }
        }
        
        // dst
        for (int i = 0; i < N; i++) {
            split = br.readLine().split("");
            for (int j = 0; j < M; j++) {
                dstMatrix[i][j] = Integer.parseInt(split[j]);
            }
        }
        
        int answer = convert();
        
        System.out.println(answer);
    }
    
    private static int convert() {
        int answer = 0;
        
        for (int i = 0; i <= N - 3; i++) {
            for (int j = 0; j <= M - 3; j++) {
                if (srcMatrix[i][j] != dstMatrix[i][j]) {
                    toggleNumber(i, j);
                    answer++;
                }
            }
        }
        
        boolean isSame = checkSame();
        
        return isSame ? answer: -1;
    }
    
    private static void toggleNumber(int x, int y) {
        for (int i = x; i < x + 3; i++) {
            for (int j = y; j < y + 3; j++) {
                srcMatrix[i][j] = srcMatrix[i][j] ^ 1; // XOR 연산으로 반전
            }
        }
    }
    
    private static boolean checkSame() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (srcMatrix[i][j] != dstMatrix[i][j]) {
                    return false;
                }
            }
        }
        
        return true;
    }
}

회고

로직 자체는 그렇게 어렵지 않은데 문제 해결 방법을 생각해보니 코드를 보면 알겠지만 4중 반복문이 떠올랐다. 4중 반복문이 흔하게 나오지는 않으니 뭔가 다른 방법이 있을까 하고 오히려 복잡하게 생각해서 시간을 많이 썼다.