[1080번] 행렬

문제 기출 : [https://www.acmicpc.net/problem/1080]

 

풀이 방법

[그리디 알고리즘] 접근   나는 본 문제 풀이에 실패했다. 만약 성공적인 풀이를 원한다면 (Alt + ←) 꾹 눌러도 좋다.   주어진 A행렬과 B행렬의 핼과 열의 수가 적어도 3이상이어야 하기 때문에 3미만이면 -1 출력 후 종료.   주어진 A행렬과 B행렬을 비교한다. 만약 값이 서로 다르면 1, 같으면 0으로 세팅한 C행렬을 만들었다. 만약 C행렬의 모든 값이 0이면 A와 B가 동일하므로 0 출력 후 종료.   C의 행렬을 모두 0으로 만들어 주기 위한 연산의 수를 구하는 것이 우리의 목표다. 그러기 위해 3by3 행렬로 잘라서 행렬연산을 해보자. 뒤집으면 count를 세어준다. 만약 한 번밖에 연산을 하지 못하는데(ex. 1행5열) 1이 나오면 그것은 더 이상 바꿀 수 없으므로 무슨 짓을 해도 이건 불가능하다. -1 출력하고 종료하자.   마지막에 총 뒤집은 횟수를 출력하고 종료.     그런데 왜 나는 실패가 된 것인가... 분명 C도 0으로 채워진다... 내가 생각하지 못한 테스트케이스가 있나 아무리 고민해도 잘 모르겠다.....ㅠㅠ

 

 

문제 풀이

public class Main {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int answer = 0;
        
		try {
			StringTokenizer tokens = new StringTokenizer(br.readLine(), " ");
			int row = Integer.parseInt(tokens.nextToken());
			int column = Integer.parseInt(tokens.nextToken());
			if (row < 3 || column < 3) {
				System.out.println(-1);
				return;
			}

			char[][] A = new char[row][column];
			int[][] C = new int[row][column];

			for (int i = 0; i < row; i++) {
				A[i] = br.readLine().toCharArray();
			}

			char[] values = new char[column];
			int diffFlag = 0;
			for (int i = 0; i < row; i++) {
				values = br.readLine().toCharArray();
				for (int j = 0; j < column; j++) {
					if (values[j] != A[i][j]) {
						diffFlag++;
						C[i][j] = 1;
					} else {
						C[i][j] = 0;
					}
				}
			}

			if (diffFlag == 0) {
				System.out.println(0);
				return;
			}

			for (int i = 0; i <= row - 3; i++) {
				for (int j = 0; j <= column - 3; j++) {
					if (i == column + 3 && !(C[i][j] == C[i][j + 1] && C[i][j] == C[i][j + 2])
							|| i == row + 3 && !(C[i][j] == C[i + 1][j] && C[i][j] == C[i + 2][j])) {
						System.out.println(-1);
						return;
					} else {
						for (int k = i; k < i + 3; k++) {
							for (int z = j; z < j + 3; z++) {
								C[k][z] = 1 - C[k][z];
							}
						}
						answer++;
					}

				}
			}

			int flag = C[row - 3][column - 3];
			for (int k = row - 1; k > row - 3; k--) {
				for (int z = column - 1; z > column - 3; z--) {
					if (flag != C[k][z]) {
						System.out.println(-1);
						return;
					}
				}
			}

			System.out.println(answer);
		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			try {
				br.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}
}