[백준] 1080번 행렬문제 간단하게 해결하는 법 : Programming Story

1. 문제

1) 링크

www.acmicpc.net/problem/1080

2) 문제

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

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

3) 입력

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

4) 출력

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

더 자세한 문제의 입력/출력 제한사항을 보기 위해서는 위의 링크를 클릭해보자

2. 풀이

이 문제는 3*3 씩 배열을 바꿀 수 있으므로 3*3의 가장 좌측 상단의 칸을 index로 기준삼아서 만약 그 칸의 배열이 서로 다르다면 전체 3*3 칸을 바꾸어 주는 식으로 진행한다.

예시 그림

예를 들어 위와 같은 5*5 칸이 있다면 살색으로 칠해진 3*3 배열을 움직이면서 보는 것이다. 그 중에서도 좌측 상단에 남색으로 칠해있는 칸의 배열 값이 바뀌어야 한다면 전체 3*3 배열을 바꾸는 식으로 진행한다.

이렇게 진행하면 좌측 상단이기 때문에 검사를 하는 칸이 열 n개 중 n-2개, 행 m개 중 m-2개밖에 할 수 없다.

따라서 좌측 상단의 칸을 기준으로 검사를 한 뒤에 다시 한번 모든 칸에 대해 값이 일치하는지를 검사하여 가능한지의 여부를 검사하게 된다.

3. 코드

위의 설명을 코드로 나타낸 것은 아래와 같다.

import java.util.*;

public class Main{
    static int a[][];
    static void change(int x, int y){
        for(int i=x; i<=x+2; i++){
            for(int j=y; j<=y+2; j++){
                a[i][j]=1-a[i][j]; //1은 0으로, 0은 1로
            }
        }
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        a=new int[n][m];
        int b[][]=new int[n][m];
        for(int i=0; i<n; i++){
            String s=sc.next();
            for(int j=0; j<m ; j++){
                a[i][j]=s.charAt(j)-'0';
            }
        }
        for(int i=0; i<n; i++){
            String s=sc.next();
            for(int j=0; j<m ; j++){
                b[i][j]=s.charAt(j)-'0';
            }
        }
        int count=0;
        for(int i=0; i<n-2; i++){
            for(int j=0; j<m-2; j++){
                if (a[i][j]!=b[i][j]){
                    count++;
                    change(i,j);
                }
            }
        }
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if (a[i][j]!=b[i][j]){
                    System.out.println(-1);
                    System.exit(0);
                }
            }
        }
        System.out.println(count);
    }
}