백준 - 1080. 행렬

앞으로는 정리하면 좋을 것 같다고 생각이 드는 문제에 대해 글을 남길 계획이다.

 

1080. 행렬

 

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

1080번: 행렬

 

입출력

 

설명

행렬의 크기 N, M과 두 행렬 A, B가 주어진다.

A를 B와 동일하게 만들기 위해 3*3 크기의 부분 행렬을 뒤집는 최소 연산 횟수를 출력해야 한다.

만약 동일하게 만들 수 없다면 -1을 출력해야 한다.

 

접근

실버 1 문제라서 무난하겠거니 생각했는데 문제를 아무리 읽어도 방법이 떠오르지 않아서 고생했다.

대부분의 문제들이 그렇듯 눈으로는 정말 쉽게 풀겠는데 막상 코드 작성은 하지 못하는 경우였다.

 

주변에서 그리디 알고리즘(Greedy Algorithm)이라는 힌트를 받고서야 풀 수 있었다.

 

풀이

3*3 크기의 부분 행렬에 있는 모든 원소를 뒤집는다는 점을 활용해야 한다.

이 말의 의미는 아래와 같이 3*3 미만 크기의 행렬만큼 뒤집을 수 없다는 것이다.

따라서 (0,0) 위치의 원소를 뒤집기 위해선 반드시 (1,1)을 중심으로 하는 부분 행렬을 뒤집어야 한다.

 

즉, 중심에서 왼쪽 위의 값이 같으면 뒤집지 않고 다르면 뒤집으면 된다.

 

그 후 A와 B를 비교했을 때 내용이 다르다면 동일하게 만들 수 없다고 판단해 -1을 반환한다.

 

코드

initMap: 행렬을 입력 값에 맞게 초기화한다.

changeMap: 왼쪽 위의 값이 다르면 3*3 만큼을 뒤집는다.

checkMap: 결과를 비교한다.

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

public class Main {

    static boolean[][] map;
    static boolean[][] result;
    static int N;
    static int M;

    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(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = initMap(br);
        result = initMap(br);

        int answer = 0;
        for(int i = 1; i < N-1; i++) {
            for(int j = 1; j < M-1; j++) {
                if(map[i-1][j-1] != result[i-1][j-1]) {
                    changeMap(i, j);
                    answer++;
                }
            }
        }

        if(checkMap()) {
            bw.append(String.valueOf(answer));
        } else {
            bw.append("-1");
        }
        bw.flush();
    }

    static boolean[][] initMap(BufferedReader br) throws IOException {
        boolean[][] map = new boolean[N][M];
        for(int i = 0; i < N; i++) {
            String temp = br.readLine();
            for(int j = 0;j < M; j++){
                map[i][j] = temp.charAt(j) - '0' != 0;
            }
        }
        return map;
    }

    static void changeMap(int n, int m) {
        for(int i = n-1; i <= n+1; i++) {
            for(int j = m-1; j <= m+1; j++) {
                map[i][j] = !map[i][j];
            }
        }
    }

    static boolean checkMap() {
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(map[i][j] != result[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
}