백준 1080. 행렬

0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.
행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0)

 

• 이 문제가 그리디 알고리즘인 이유

Q1. 3 * 3행렬로 가장 많이 변경할 수 있는 것이 최적의 해가 아닌가요? 많이 변경함으로써 전체적으로 변경해야할 수가 줄어든 거니깐요.

→ 뒤집는 연산의 특성상 많이 변경하는 것은 의미가 없습니다. 따라서 최적의 해에 가까워진다고 볼 수 없습니다.

 

Q2. 이게 왜 최적의 해가 되는 건가요? 그냥 순서대로 뒤집어 보다가 단순히 맞추는 것이 아닌가요? 그것이 어떻게 최저횟수가 되는지 모르겠습니다.

→ 이 문제의 목적은 행렬 A를 행렬 B로 바꾸는 것입니다. 따라서 행렬 A에서 0인데 B에서 1인 칸이 있으면 반드시 뒤집어야 합니다.

문제는 그 연산을 몇 번 하느냐입니다. 뒤집는 연산의 특성상 2번 이상 뒤집는 것은 의미가 없습니다. 2번 뒤집으면 원래대로 돌아오고, 3번 뒤집는 것은 1번 뒤집는 것과 같습니다.

이때 최적의 선택은 "반드시 뒤집어야 하는 칸을 뒤집되, 뒤집는 횟수를 최소화하는 것" 입니다. 즉, 이미 뒤집은 칸을 2번이나 3번 뒤집지 않습니다.

이 전략은 다음과 같이 구현됩니다. 행렬을 순서대로 탐색하면서, "반드시 뒤집어야 하는 부분이 있으면" 바꿉니다. 뒤집을 필요가 없으면 확정하고 넘어갑니다.

 

그러다 어떤 칸을 만났는데 그 칸을 뒤집으면 이전에 확정시켜 놓은 칸이 다시 뒤집힐 경우, 살펴보지 않고 넘어갑니다.

 

 

이렇게 하면 5 × 5 행렬의 경우, 좌상단부터 3 × 3 부분에 있는 칸만 확정해도 이 행렬을 B로 변환 가능한지 아닌지를 알 수 있습니다.

이 알고리즘은 매 순간 ‘뒤집어야 하는 칸의 뒤집는 횟수를 최소화한다’는 점에서 그리디 알고리즘으로 분류된다고 생각합니다.

 

(출처: 백준 질문)

 

• 두개의 배열을 비교해서 같으면 true 다르면 false의 boolean배열을 생성해준다.
• boolean배열을 탐색하면서 행 N-3, 열 M-3까지 반복을 돌리면서 값이 false면 3*3만큼 false->true / true->false로 변경해준다.
  • 변경해줄때마다 변경해줬다고 cnt++ 을 해줘서 카운트 한다.
• 전체를 돌린 후 boolean값이 전부 true이면 cnt값을 출력하고 하나라도 false인 부분이 있으면 변경되지 않는 행렬이므로 -1을 출력한다.
• 제약조건

3X3행렬보다 작은 행렬은 -1이 나와야 한다.

반례 : 1 2

0 0

0 1

답 : -1

3X3행렬보다 작은 행렬이라도 두 행렬이 같으면 0을 출력해준다. (이 부분에서 계속 틀렸다.)

반례 : 1 2

0 1

0 1

답 : 0

 

package greedy;

import java.util.*;
import java.io.*;

public class Main_실버2_1080_손은성 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int cnt = 0;
		int drawCnt = 0;
		int arrN[][] = new int[N][M];
		int arrM[][] = new int[N][M];
		boolean arrCheck[][] = new boolean[N][M];

		// N 데이터 입력
		for (int i = 0; i < N; i++) {
			String strN = br.readLine();
			for (int j = 0; j < M; j++) {
				arrN[i][j] = strN.charAt(j) - '0';
			}
		}
		// M 데이터 입력
		for (int i = 0; i < N; i++) {
			String strN = br.readLine();
			for (int j = 0; j < M; j++) {
				arrM[i][j] = strN.charAt(j) - '0';
				if (arrN[i][j] == arrM[i][j]) {
					arrCheck[i][j] = true;
					drawCnt++;
				}
			}
		}
		// 행렬이 3보다 작을 때
		if (N < 3 && M < 3) {
			// 두 행렬이 같으면 0 출력
			if (drawCnt == N * M)
				System.out.println(0);
			// 두 행렬이 다르면 -1 출력
			else
				System.out.println(-1);
		} 
		
		// 행렬이 3보다 클 때
		else {
			for (int i = 0; i <= N - 3; i++) {
				for (int j = 0; j <= M - 3; j++) {
					if (!arrCheck[i][j]) { // check배열이 false라면 (변경해 줘야 한다면)
						for (int i2 = i; i2 < i + 3; i2++) { // check부터 시작해서 3X3만큼 값 변경
							for (int j2 = j; j2 < j + 3; j2++) {
								arrCheck[i2][j2] = arrCheck[i2][j2] == true ? false : true; // 삼항 연산자 이용하여 true->false, false->true로 변경
							}
						}
						cnt++; // 한번 뒤집을 때 마다 count 1씩 증가
					}
				}
			}
			
			// boolean배열 체크
			Loop1: for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					// 하나라도 false가 있으면 -1 출력
					if (!arrCheck[i][j]) {
						System.out.println(-1);
						break Loop1;
					} 
					// 전부 확인 후 true이면 cnt출력
					else if (i == N - 1 && j == M - 1) {
						System.out.println(cnt);
					}
				}
			}
		}
	}
}

 

 

 

✅ 후기

• 그리디 알고리즘에 대한 개념은 점점 잡혀가고 문제를 어떤방식을 이용해서 풀어야 하는지는 이해가 가는데 실제로 구현하는 능력이 많이 부족한 것 같다.
• 배열 2개를 비교해서 boolean배열을 생성해서 풀 것과, N-3,M-3까지 배열을 돌려야하는것 들을 생각해 냈지만 정작 그리디 알고리즘을 이용하여 어떻게 구현해야 하는지에 대한 부분을 해결하지 못하여서 구글을 찾아보았다. 앞으로 생각한 것을 직접 구현할 수 있도록 더 공부하고 노력해야겠다.