[백준] 1080_행렬 / 그리디

 

 

Sliver

 

 

문제

 

0과 1로만 이루어진 행렬 A와 행렬 B가 있다.

이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.

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

 

 

입력

 

첫째 줄에 행렬의 크기 N M이 주어진다.

N과 M은 50보다 작거나 같은 자연수이다.

둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.

 

 

출력

 

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

 

 

---

 

풀이

 

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

class Main {
    static int N ;
    static int M ;
    static int[][] arr1 ;
    static int[][] arr2 ;
    
    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());
        arr1 = new int[N][M];
        arr2 = new int[N][M];

        for(int i=0; i<N; i++){
            String row = br.readLine();
            for(int j=0; j<M; j++){
                arr1[i][j] = row.charAt(j)-'0';
            }
        }
        
        for(int i=0; i<N; i++){
            String row = br.readLine();
            for(int j=0; j<M; j++){
                arr2[i][j] = row.charAt(j)-'0';
            }
        }

        int count = 0; 
        // 그리디
        for(int i=0; i<=N-3; i++){
            for(int j=0; j<=M-3; j++){
                // 현재 위치 값이 서로 다르면 필터 적용 -> 그리디 
                if(arr1[i][j] != arr2[i][j]){
                    count += 1;
                    filter(i, j, arr1);
                }
            }
        }

        if(!checkArr(arr1, arr2)) System.out.print(-1);
        else System.out.print(count);
        
    }

	// 3x3 배열을 뒤집는 필터
    public static void filter(int x, int y, int[][] arr){
        for(int i=x; i<x+3; i++){
            for(int j=y; j<y+3; j++){
                arr[i][j] = (arr[i][j]+1)%2;
            }
        }
    }

	// 두 배열을 비교
    public static boolean checkArr(int[][] A, int[][]B){
        for(int i=0; i<A.length; i++){
            for(int j=0; j<A[0].length; j++){
                if(A[i][j] != B[i][j]){
                    return false;
                }
            }
        }
        return true;
    }
}

 

해결방법

 

• N과 M을 입력받은 후 두 행렬에 대한 데이터를 arr1과 arr2에 저장한다.
• 두 행렬을 왼쪽 위에서부터 차례대로 탐색한다. 
• 현재 위치에서의 값이 서로 다르면 카운트를 증가시키고, 현재 위치 기준 3x3 행렬을 뒤집는다
  -> 현재 위치에서 차이가 나면 즉시 행렬을 뒤집는다. (현재 위치에서 항상 최선의 선택을 한다 ->그리디)
• 모든 연산이 끝난 후 arr1와 arr2가 같은지 확인한다. 
• 같다면 카운트를 출력하고, 다르면 -1를 출력한다. 

 

 

---

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