[BaekJoon] 1080 행렬

1.  문제 링크

2.  문제

요약

• 0과 1로만 이루어진 행렬 A, B가 있는데 3 * 3 크기의 부분 행렬에 있는 모든 원소를 뒤집어 A를 B로 바꾸는 데에 필요한 연산의 최소 횟수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 50보다 작거나 같은 자연수인 행렬의 크기 N, M이 주어지고 두 번째 줄부터 N개의 줄에는 행렬 A가 주어지고 그 다음 줄부터 N개의 줄에는 행렬 B가 주어집니다.
• 출력: A를 B로 바꾸는 데에 필요한 연산의 최소 횟수를 출력합니다.

3.  소스코드

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[][] matrix;
	static int[][] result_matrix;
	
	public int getMinConvert() {
		int count = 0;
		for(int i = 0; i < matrix.length - 2; i++) {
			for(int j = 0; j < matrix[i].length - 2; j++) {
				if(matrix[i][j] != result_matrix[i][j]) {
					for(int k = i; k < i + 3; k++) {
						for(int l = j; l < j + 3; l++) {
							if(matrix[k][l] == 1) {
								matrix[k][l] = 0;
							} else {
								matrix[k][l] = 1;
							}
						}
					}
					count++;
				}
			}
		}
		
		for(int i = 0; i < matrix.length; i++) {
			for(int j = 0; j < matrix[i].length; j++) {
				if(matrix[i][j] != result_matrix[i][j]) {
					return -1;
				}
			}
		}
		return count;
	}
	
	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 input = br.readLine();
		StringTokenizer st = new StringTokenizer(input);
		int row = Integer.parseInt(st.nextToken());
		int col = Integer.parseInt(st.nextToken());
		matrix = new int[row][col];
		result_matrix = new int[row][col];
		for(int i = 0; i < row; i++) {
			input = br.readLine();
			for(int j = 0; j < col; j++) {
				matrix[i][j] = input.charAt(j) - '0';
			}
		}
		for(int i = 0; i < row; i++) {
			input = br.readLine();
			for(int j = 0; j < col; j++) {
				result_matrix[i][j] = input.charAt(j) - '0';
			}
		}
		br.close();
		Main m = new Main();
		bw.write(m.getMinConvert() + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 이 문제는 그리디 알고리즘을 이용하여 (0, 0)부터 시작하여 (N - 3, M - 3)까지 3 * 3 행렬을 확인하고 변경해가며 B와 똑같이 변경하고 그 때의 횟수를 구하는 문제입니다.

1. 행렬 A에 대해서 (0, 0)부터 시작하여 오른쪽 아래로 진행해가며 3 * 3 행렬을 변경합니다.
2. 행렬을 바꿀 때에는 해당 3 * 3 행렬에서 왼쪽 위의 값을 기준으로 A와 B가 같은지 확인하여 다르다면 변경합니다.

• 이렇게 진행한 이유는 3 * 3 행렬에서 왼쪽 위의 값은 그 행렬에 도달했을 때에만 변경할 수 있기 때문입니다.