[BOJ] 1080 행렬 (Java)

 

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

<아이디어>

A 배열을 차례대로 탐색하다가 B 배열과 다른 부분에서 3x3 만큼을 뒤집는다.

종료후, B 배열과 동일한지 확인한다.

 

<간과했던 부분>

(0, 0)부터 (n-1, m-1)범위의 값을 모두 비교하고 뒤집었는데, 제출하니 틀렸다.

무조건 3x3 배열만큼을 뒤집어야 하기에 아래와 같이 설정해야 한다.

또한, 배열 크기가 3미만이지만 A 배열과 B 배열이 애초에 동일한 경우에는 0으로 결과값이 나와야 한다.

for(int i=0; i<n-2; i++){
            for(int j=0; j<m-2; j++){
            }
}

 

<최종 아이디어>

1. A 배열과 B 배열과 동일하면 0 출력

2. 입력 받은 배열의 크기가 3미만이면 -1 출력

3. (0, 0) 부터 (n-3, m-3) 까지 탐색하며 B 배열과 다른 값을 찾으면 A배열의 해당 위치부터 3X3 만큼 뒤집는다. 

4. A배열과 B배열을 비교하며 같으면 뒤집은 수(cnt)를 출력하고, 다르면 -1을 출력한다.

 

<제출 코드>

package BOJ.Greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_1080_행렬 {

    static int n, m;
    static int cnt;
    static char[][] arr1, arr2;

    public static boolean check(){
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(arr1[i][j] != arr2[i][j]) return false;
            }
        }
        return true;
    }

    public static void reverse(){
        for(int i=0; i<n-2; i++){
            for(int j=0; j<m-2; j++){
                // 해당 위치의 두 배열 값이 다르면 3x3 뒤집음
                if(arr1[i][j] != arr2[i][j]){
                    for(int k=i; k<i+3; k++){
                        for(int h=j; h<j+3; h++){
                            if(arr1[k][h] == '0') arr1[k][h] = '1';
                            else arr1[k][h] = '0';
                        }
                    }
                    cnt++;
                }
            }
        }
    }

    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 char[n][m];
        arr2 = new char[n][m];
        for(int i=0; i<n; i++) arr1[i] = br.readLine().toCharArray();
        for(int i=0; i<n; i++) arr2[i] = br.readLine().toCharArray();
        if(check()) System.out.println(0);			// 입력 배열이 같으면
        else if(n<3 || m<3) System.out.println(-1);	// 크기가 3 미만이면 -1
        else{
            reverse();
            if(!check()) System.out.println(-1);
            else System.out.println(cnt);
        }
    }
}