[백준] 1080 행렬 - Greedy / Java

• 문제 링크

1080번: 행렬

 

• 풀이 과정

두 행렬을 비교하여 특정 좌표에 다른 값이 존재할 경우

문제에 제시된 조건에 따라 해당 좌표가 (0, 0) 이 되는 3 * 3 크기의 부분 행렬을 모두 뒤집는다.

 

이때 전체 범위 중 부분 행렬을 뒤집을 때 배열의 범위를 벗어나지 않기 위해

n - 2 * m - 2 의 범위에서 해당 좌표의 값이 서로 다른지 탐색한다.

 

이때 값이 다를 경우 연산의 횟수를 의미하는 cnt++ 를 수행 및 해당 좌표를 (0, 0) 으로 지정하여

3 * 3 부분 행렬의 모든 값을 XOR 연산으로 뒤집는다.

 

끝으로 두 행렬의 일치 여부를 검사하여 cnt 변수 또는 -1 을 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

	static int[][] a;

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

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		a = new int[n][m];
		int[][] b = new int[n][m];

		for (int i = 0; i < n; i++) {
			String input = br.readLine();
			for (int j = 0; j < m; j++)
				a[i][j] = input.charAt(j) - '0';
		}

		for (int i = 0; i < n; i++) {
			String input = br.readLine();
			for (int j = 0; j < m; j++)
				b[i][j] = input.charAt(j) - '0';
		}

		int cnt = 0;
		for (int i = 0; i < n - 2; i++) {
			for (int j = 0; j < m - 2; j++) {
				if (a[i][j] != b[i][j]) {
					swap(i, j);
					cnt++;
				}
			}
		}
		
		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;
				}
			}
		}
		
		bw.write((flag ? cnt : -1) + "\n");
		bw.flush();
	}

	private static void swap(int y, int x) {
		for (int i = y; i < y + 3; i++) {
			for (int j = x; j < x + 3; j++)
				a[i][j] = a[i][j] ^ 1;
		}
	}

}