[Java] 백준 1080 : 행렬

문제 링크

1.

$(0,0)$부터 끝까지 변환 후 같은지 확인하면 될 것 같은데..라고 생각했지만,

그리디 문제라서 뭔가 좀더 그리디스러운 방법이 존재할 거라고 생각했다.

 

저 방법 말고는 떠오르지가 않아 방법이 맞는지 해설을 봤더니 맞았다..

 

 

2.

내가 생각했던 데로 $(0,0$에서 부터 끝가지 변환하면 되지만 유의해야 할 점이 있다.

$3\times3$ 크기의 부분 행렬을 변환하는 것이라서 $N\times M$ 모두 확인할 필요가 없다.

$(0,0$ 에서부터 $(N-3,M-3)$ 까지만 변환하면 된다.

그 이상의 변환은 다시 원래대로 바꾸는 것이므로 불필요한 연산이 된다.

 

이것을 알았다면 구현은 쉽다.

1. $(0,0$에서부터 $(N-3,M-3)$까지 A와 B의 원소가 다르다면 $3\times3$ 크기의 부분 행렬을 변환한다.

2. 다 변환한 후 A와 B가 같은지 확인한다.

 

 

3.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        // 입력
        int[][] a = new int[n][m];
        int[][] b = new int[n][m];
        for (int i = 0; i < n; i++) {
            String temp = sc.next();

            for (int j = 0; j < m; j++) {
                a[i][j] = temp.charAt(j) - '0';
            }
        }
        for (int i = 0; i < n; i++) {
            String temp = sc.next();

            for (int j = 0; j < m; j++) {
                b[i][j] = temp.charAt(j) - '0';
            }
        }

        // 행렬 변환
        int count = 0;
        for (int i = 0; i <= n - 3; i++) {
            for (int j = 0; j <= m - 3; j++) {
                if (a[i][j] != b[i][j]) {
                    count++;
                    for (int p = i; p < i + 3; p++) {
                        for (int q = j; q < j + 3; q++) {
                            a[p][q] = (a[p][q] == 0) ? 1 : 0;
                        }
                    }
                }
            }
        }

        // 같은지 확인
        boolean flag = true;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[i][j] != b[i][j]) {
                    flag = false;
                    break;
                }
            }
        }

        System.out.println((flag) ? count : -1);

    }
}

 

 

4.

숫자 문자 char을 int로 바꾸려면 '0'을 빼주자.

 

[참고] https://plplim.tistory.com/42