[BOJ][Java] 백준 1080번: 행렬

문제 설명

0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오. 행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0)

 

문제 풀이

저는 처음 이 문제를 고민할 때 제일 최적화된 답을 어떻게 찾을까? 제일 겹치는 범위가 큰 곳을 찾아서 뒤집어야할까? 라는 고민이였습니다. 하지만 위의 방법처럼 코드를 구현하면 적절한 위치를 찾는데에 시간이 소요되기 때문에 좋지 않은 코드가 됩니다.

그렇다면 어떻게 해야할까요? 방법은 단순합니다.

3x3 범위를  비교하면서 하나라도 다른 곳이 있으면 뒤집는 것입니다.  이것때문에 이 문제가 그리디 알고리즘이 아닌가 싶습니다.

만약에 탐색이 끝났는데도 A와 B가 같지않다면 -1을 반환해주는 조건을 마지막에 추가해주시면 해결됩니다.

 

풀이 코드

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static int N, M, ans = 0;
    static int[][] A, B;

    private static void input() throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        A = new int[N][M];
        B = new int[N][M];

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

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

    private static void process() throws IOException{
        if(N<3 || M <3){
            if(isSame(A, B)) ans = 0;
            else ans = -1;
        }else{
            findRange();
            if(!isSame(A, B)) ans = -1;
        }
        System.out.println(ans);
    }

    private static void findRange() {
        for(int i=0; i<N-2; i++){
            for(int j=0; j<M-2; j++){
                if(A[i][j] != B[i][j]){
                    flip(i, j);
                    ans+=1;
                }
            }
        }
    }

    private static void flip(int r, int c){
        for(int i=r; i<r+3; i++){
            for(int j=c; j<c+3; j++){
                A[i][j] = A[i][j] == 1 ? 0 : 1;
            }
        }
    }

    private static boolean isSame(int[][] A, int[][] B){
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(A[i][j] != B[i][j]) return false;
            }
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        input();
        process();
    }
}

 

<출처>

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

1080번: 행렬