[알고리즘-PS] 백준 1080번 행렬 자바 문제풀이

문제

해당 포스팅은 백준의 1080번 행렬 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

 

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

 

문제 접근

 

이번 문제는 그리디 알고리즘을 적용하면 해결할 수 있는 문제이다.

 

문제에서는 시작 행렬과 타깃 행렬을 입력으로 주어진다.

 

3 by 3의 부분 행렬 을 비트 반전 시켰을 때, 최소 몇 번의 반전을 시켜야 타깃 행렬과 동일하게 되는지 최소 회수를 구하는 문제이다.

 

해결법

 

n by m 행렬이 있다면 배열 원소 하나씩 iteration 하면서 start 행렬과 target 행렬의 원소가 동일하다면 넘어가고 동일하지 않다면 flip 하면 된다.

 

정답 코드

 

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] nm = br.readLine().split(" ");

        int n = Integer.parseInt(nm[0]);
        int m = Integer.parseInt(nm[1]);

        int[][] start = new int[n][m];
        int[][] target = new int[n][m];

        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split("");
            for (int j = 0; j < m; j++) {
                start[i][j] = Integer.parseInt(line[j]);
            }
        }
        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split("");
            for (int j = 0; j < m; j++) {
                target[i][j] = Integer.parseInt(line[j]);
            }
        }

        int answer = 0;

        if(n < 3 || m < 3) {
            if(Arrays.deepEquals(start, target)) {
                bw.write("0");
            }else {
                bw.write("-1");
            }
            bw.flush();            
            return;
        }

        boolean flag = false;

        if(Arrays.deepEquals(start, target)) {
            flag = true;
        }else {
            mainLoop: for (int i = 0; i < n - 2; i++) {

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

                    if(start[i][j] != target[i][j]) {
                        for (int k = i; k <= i + 2; k++) {
                            for (int l = j; l <= j + 2; l++) {
                                start[k][l] = (start[k][l] == 1) ? 0 : 1;
                            }
                        }
                        answer++;
                    }

                    if(Arrays.deepEquals(start, target)) {
                        flag = true;
                        break mainLoop;
                    }
                }
            }
        }

        // count 출력
        if(flag && Arrays.deepEquals(start, target)) {
            bw.write(String.valueOf(answer));
        }else {
            bw.write("-1");
        }

        bw.flush();
        bw.close();
    }
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.