백준 1080번: 행렬 (C++ 풀이)

🔷 백준 1080번: 행렬 (C++ 풀이)

문제 설명

문제

0과 1로만 이루어진 행렬 A와 행렬 B가 주어집니다. 행렬 A를 행렬 B로 변환하기 위해 필요한 최소 연산 횟수를 구하는 프로그램을 작성하세요. 여기서 연산은 3×3 크기의 부분 행렬에 있는 모든 원소를 뒤집는 것입니다. (0 → 1, 1 → 0)

입력

• 첫째 줄에 행렬의 크기 N과 M이 주어집니다. (N, M은 50 이하의 자연수)
• 둘째 줄부터 N개의 줄에 행렬 A가 주어집니다.
• 그 다음 N개의 줄에 행렬 B가 주어집니다.

출력

• 행렬 A를 행렬 B로 변환하기 위한 최소 연산 횟수를 출력합니다.
• 변환할 수 없는 경우 -1을 출력합니다.

테스트 케이스

1. 예제 입력 1

3 4
0000
0010
0000
1001
1011
1001

예제 출력 1

2

2. 예제 입력 2

3 3
111
111
111
000
000
000

예제 출력 2

1

3. 예제 입력 3

1 1
1
0

예제 출력 3

-1

4. 예제 입력 4

18 3
001
100
100
000
011
010
100
100
010
010
010
110
101
101
000
110
000
110
001
100
011
000
100
010
011
100
101
101
010
001
010
010
111
110
111
001

예제 출력 4

7

문제 설명

이 문제는 행렬 A를 행렬 B로 변환하기 위해 필요한 최소 3×3 부분 행렬 뒤집기 연산의 횟수를 구하는 것입니다. 주요 제약 조건은 다음과 같습니다:

• 행렬 크기는 N×M이며, N, M은 50 이하입니다.
• 연산은 3×3 부분 행렬을 선택해 모든 원소를 뒤집는 방식입니다.
• 변환할 수 없는 경우 -1을 출력해야 합니다.

정답인 경우

• 행렬 A를 연산을 통해 행렬 B와 동일하게 만들 수 있으면 최소 연산 횟수가 답입니다.
• 예제 1의 경우, (0,0)과 (0,1) 위치에서 3×3 부분 행렬을 뒤집으면 A가 B와 동일해지므로 답은 2입니다.
• 예제 2의 경우, (0,0) 위치에서 한 번의 연산으로 모든 원소가 1에서 0으로 바뀌므로 답은 1입니다.

오답인 경우

• 행렬 A를 어떤 연산으로도 B로 만들 수 없을 때 -1을 출력합니다.
• 예제 3의 경우, 행렬 크기가 1×1이므로 3×3 부분 행렬을 만들 수 없어 변환 불가능(-1 출력).
• 행렬 크기가 3×3 이상이더라도, 연산 후에도 A와 B가 다르면 -1을 출력합니다.

사례 중심 논증

• 예제 1: 3×4 행렬에서 (0,0)과 (0,1) 위치에서 연산을 수행하면 A가 B와 동일해집니다. 각 연산은 3×3 영역의 9개 원소를 뒤집으므로, 겹치는 영역을 고려해 전략적으로 선택해야 합니다.
• 예제 3: 1×1 행렬은 3×3 연산을 적용할 수 없으므로 변환 불가능입니다.
• 예제 4: 18×3 행렬은 세로가 길지만 가로가 3이므로 연산은 첫 번째 열에서만 가능합니다. 여러 위치에서 연산을 수행해 최종적으로 B와 일치하도록 만듭니다.

아이디어

🎯 문제의 목적

주어진 두 개의 5×5 행렬이 있습니다. 목표는 arr1을 arr2와 완전히 같게 만드는 것입니다.

단, 우리가 사용할 수 있는 유일한 연산은 다음과 같습니다:

아무 위치 (i,j)를 좌상단 기준으로 3×3 부분 행렬 전체를 뒤집는 것 (즉, 해당 9칸의 0은 1로, 1은 0으로 모두 반전됩니다)

📌 시작 상태

arr1:                     arr2:
1★ 0 0 0 1                 0★ 1 1 0 1
1  0 1 0 0                 0  1 0 0 0
0  0 1 0 1                 1  1 0 0 1
0  0 0 0 0                 0  0 0 1 1
1  1 1 1 1                 1  1 1 0 0

🔍 현재 비교 위치: (0,0)

• arr1[0][0] = 1
• arr2[0][0] = 0

→ 두 값이 서로 다릅니다.

→ 이 위치를 좌상단으로 하는 3×3 영역을 지금 즉시 뒤집지 않으면, 이 칸 (0,0)은 이후에는 어떤 연산으로도 다시 수정할 수 없게 됩니다.

→ 따라서 이 지점에서 반드시 flip을 수행해야 합니다.

✅ flip 수행: 기준 좌표 (0,0)

arr1:                     arr2:
0★ 1 1 0 1                 0★ 1 1 0 1
0  1 0 0 0                 0  1 0 0 0
1  1 0 0 1                 1  1 0 0 1
0  0 0 0 0                 0  0 0 1 1
1  1 1 1 1                 1  1 1 0 0

📘 설명

• (0,0)의 값이 1에서 0으로 뒤집혀 arr2[0][0]과 같아졌습니다.
• 동시에 (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)까지 3×3 범위의 값들이 전부 반전되었습니다.
• 이 flip은 해당 칸들을 수정할 수 있는 유일한 기회였으며, 지금 수행했기 때문에 해당 좌표들이 일부 또는 전부 arr2와 일치하게 되었습니다.
• 즉, 현재 flip은 arr1을 arr2에 맞추기 위한 필수 연산이었습니다.

❌ 만약 (0,0)을 flip하지 않고 넘어갔다면?

→ 지금 flip을 하지 않고 (0,1)로 이동했을 경우입니다.

→ 그에 따른 배열 상태는 다음과 같습니다:

arr1:                     arr2:
[1]  0★ 0 0 1               [0]  1★ 1 0 1
 1   0  1 0 0                0   1  0 0 0
 0   0  1 0 1                1   1  0 0 1
 0   0  0 0 0                0   0  0 1 1
 1   1  1 1 1                1   1  1 0 0

• 이 상태에서 arr1[0][1]과 arr2[0][1]이 다르기 때문에 flip을 시도하게 됩니다.
• 하지만 기준 좌표가 (0,1)이므로 flip 범위는 (0,1)에서 (2,3)까지입니다.
• 결과적으로 (0,0)은 flip 범위에 포함되지 않습니다.
• 다시 말해, (0,0)은 앞으로도 절대로 뒤집힐 수 없는 좌표가 됩니다.

→ 아래는 flip을 실제 수행한 이후의 상태입니다:

❌ (0,1)에서 flip 수행한 경우

arr1:                     arr2:
[1]  1★ 1 1 1               [0]  1★ 1 0 1
 1   1  0 1 0                0   1  0 0 0
 0   1  0 1 1                1   1  0 0 1
 0   0  0 0 0                0   0  0 1 1
 1   1  1 1 1                1   1  1 0 0

📘 설명

• 위와 같이 (0,1)에서 flip을 수행하면, 그 범위는 (0,1)~(2,3)이기 때문에 (0,0)은 포함되지 않고 그대로 남아 있습니다.
• 즉, arr1[0][0] = 1, arr2[0][0] = 0 → 여전히 다릅니다.
• 이 상태는 어떤 다음 연산을 하더라도 절대로 해결되지 않습니다.
• (0,0)은 flip을 하지 않은 순간, 다시는 손댈 수 없는 고정 오류가 되어버린 것입니다.
• 이로 인해 최종적으로 arr1과 arr2는 절대로 같아질 수 없습니다.

풀이 아이디어 정리

1. 왼쪽 위에서 오른쪽 아래로, 순차적으로 하나씩 비교하면서 진행한다

• arr1과 arr2를 완전히 동일하게 만들기 위해서는 좌상단부터 우하단까지 차례로 순회해야 합니다.
• 순서를 어기면 안 됩니다. 왜냐하면 뒤집기(flip)는 3×3 전체를 한꺼번에 바꾸기 때문에, 이미 지나친 칸은 다시 되돌릴 수 없습니다.
• 즉, "지금 다르면 지금 해결해야만 한다"는 전략을 반드시 따릅니다.

2. 어떤 좌표 (i,j)에서 arr1[i][j]와 arr2[i][j]가 다르다면 → flip은 반드시 그 자리에서 지금 수행해야 한다

• 3×3 flip은 (i,j)를 좌상단으로 한 3행 3열만을 변경할 수 있기 때문에, 지금 이 칸을 포함하는 flip은 지금밖에 할 수 없습니다.
• 만약 지금 이 차이를 flip하지 않고 넘어가면, 나중에 다시는 이 칸을 포함해서 flip할 수 없습니다.
• 따라서 이 문제는 "그리디(Greedy)" 전략으로 푸는 것이 맞다는 논증이 성립합니다.

3. flip은 arr1을 arr2에 맞추는 방식으로만 수행된다 (arr2는 절대로 바꾸지 않는다)

• arr2는 "정답 상태"이므로, 우리가 맞춰야 하는 쪽은 arr1입니다.
• arr1을 직접 flip하며 arr2와 점점 같게 만들어가야 합니다.
• 이때, flip의 결과가 일부 칸을 맞게 만들기도 하고, 이미 맞은 걸 틀리게 만들기도 하지만, 우리는 전체적인 흐름에 따라 반드시 지금 이 차이는 지금 해결해야만 합니다.

4. 모든 flip을 수행한 후, 두 배열이 완전히 같아졌는지 검사한다

• 마지막에 arr1과 arr2를 한 칸씩 다시 비교합니다.
• 만약 단 하나라도 다르면, 그건 이미 지나간 칸에서 flip을 놓친 경우입니다.
• 따라서 이 경우는 문제 조건상 절대로 arr2와 같아질 수 없으므로 -1을 출력해야 합니다.

전체 코드

#include 

using namespace std;

void turn_arr(int arr[][50], int start_i, int start_j) {
    for (int i = start_i; i < 3 + start_i; i++) {
        for (int j = start_j; j < 3 + start_j; j++) {
            arr[i][j] = (arr[i][j] == 1) ? 0 : 1;
        }
    }
}

bool check_arr(int arr1[][50], int arr2[][50], int size1, int size2) {
    for (int i = 0; i < size1; i++) {
        for (int j = 0; j < size2; j++) {
            if (arr1[i][j] != arr2[i][j]) return false;
        }
    }
    return true;
}

int main(void) {
    int N, M, cnt = 0;
    int arr1[50][50];
    int arr2[50][50];
    char line[51];
    cin >> N >> M;
    
    for (int i = 0; i < N; i++) {
        cin >> line;
        for (int j = 0; j < M; j++)
            arr1[i][j] = line[j] - '0';
    }
    for (int i = 0; i < N; i++) {
        cin >> line;
        for (int j = 0; j < M; j++)
            arr2[i][j] = line[j] - '0';
    }
    
    if (喧 (N < 3 || M < 3) {
        if (check_arr(arr1, arr2, N, M)) cout << 0 << endl;
        else cout << -1 << endl;
        return 0;
    }
    
    for (int i = 0; i <= N - 3; i++) {
        for (int j = 0; j <= M - 3; j++) {
            if (arr1[i][j] != arr2[i][j]) {
                turn_arr(arr1, i, j);
                cnt++;
            }
        }
    }
    
    if (check_arr(arr1, arr2, N, M)) cout << cnt << endl;
    else cout << -1 << endl;
    
    return 0;
}

개별 코드 설명

1. 3×3 부분 행렬 뒤집기 함수 (turn_arr)

void turn_arr(int arr[][50], int start_i, int start_j) {
    for (int i = start_i; i < 3 + start_i; i++) {
        for (int j = start_j; j < 3 + start_j; j++) {
            arr[i][j] = (arr[i][j] == 1) ? 0 : 1;
        }
    }
}

• 설명: 주어진 (start_i, start_j)를 왼쪽 상단으로 하는 3×3 부분 행렬의 모든 원소를 뒤집습니다. 0은 1로, 1은 0으로 변경합니다.
• 역할: 연산의 핵심 동작을 수행하며, 행렬 A의 특정 영역을 수정합니다.

2. 행렬 비교 함수 (check_arr)

bool check_arr(int arr1[][50], int arr2[][50], int size1, int size2) {
    for (int i = 0; i < size1; i++) {
        for (int j = 0; j < size2; j++) {
            if (arr1[i][j] != arr2[i][j]) return false;
        }
    }
    return true;
}

• 설명: 행렬 A와 B를 비교해 모든 원소가 동일한지 확인합니다. 동일하면 true, 다르면 false를 반환합니다.
• 역할: 변환 후 A와 B가 같은지 확인해 결과 출력 여부를 결정합니다.

3. 입력 처리

int N, M, cnt = 0;
int arr1[50][50];
int arr2[50][50];
char line[51];
cin >> N >> M;
for (int i = 0; i < N; i++) {
    cin >> line;
    for (int j = 0; j < M; j++)
        arr1[i][j] = line[j] - '0';
}
for (int i = 0; i < N; i++) {
    cin >> line;
    for (int j = 0; j < M; j++)
        arr2[i][j] = line[j] - '0';
}

• 설명: N과 M을 입력받고, 행렬 A와 B를 문자열로 입력받아 정수 배열로 변환합니다. line[j] - '0'를 사용해 문자 '0' 또는 '1'을 정수 0 또는 1로 변환합니다.
• 역할: 문제의 입력 데이터를 프로그램에서 사용할 수 있도록 준비합니다.

4. 크기 제약 확인

if (N < 3 || M < 3) {
    if (check_arr(arr1, arr2, N, M)) cout << 0 << endl;
    else cout << -1 << endl;
    return 0;
}

• 설명: 행렬 크기가 3×3 미만이면 3×3 연산을 수행할 수 없습니다. 이 경우 A와 B가 이미 동일하면 0을, 다르면 -1을 출력하고 종료합니다.
• 역할: 예제 3과 같은 특수 케이스를 처리합니다.

5. 메인 로직

for (int i = 0; i <= N - 3; i++) {
    for (int j = 0; j <= M - 3; j++) {
        if (arr1[i][j] != arr2[i][j]) {
            turn_arr(arr1, i, j);
            cnt++;
        }
    }
}

• 설명: (0,0)부터 (N-3, M-3)까지 순회하며, A[i][j]와 B[i][j]가 다르면 해당 위치에서 3×3 연산을 수행하고 연산 횟수(cnt)를 증가시킵니다.
• 역할: 그리디 방식으로 필요한 연산을 수행합니다.

6. 결과 출력

if (check_arr(arr1, arr2, N, M)) cout << cnt << endl;
else cout << -1 << endl;

• 설명: 모든 연산 후 A와 B가 동일하면 연산 횟수를 출력하고, 다르면 -1을 출력합니다.
• 역할: 최종 결과를 출력합니다.

결론

• 그리디 알고리즘의 효과적 적용: 이 문제는 왼쪽 상단부터 순차적으로 차이를 제거하는 그리디 접근이 효과적입니다.
• 제약 조건 처리: 행렬 크기가 3×3 미만인 경우를 별도로 처리해 예외 상황을 해결했습니다.
• 효율적인 연산: 각 위치에서 필요한 경우에만 연산을 수행해 최소 횟수를 보장합니다.
• 확장 가능성: 이 코드는 N, M이 50 이하인 모든 입력에 대해 동작하며, 일반적인 행렬 변환 문제에 적용 가능합니다.