[C언어] 백준 1080 : 행렬

백준 1080 : 행렬

 

문제 링크

www.acmicpc.net/problem/1080

1080번: 행렬

 

 

문제 내용

0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.

행렬을 변환하는 연산은 어떤 3*3 크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 -> 1, 1 -> 0)

 

 

Idea

행렬 A를 행렬 B로 바꾸는데 필요한 최소 연산 횟수를 구하는 문제이다.

 

이때, 연산이란 3*3 크기의 부분 행렬의 원소를 모두 뒤집는 것을 의미한다. 즉, 행렬의 크기가 3*3보다 작다면 뒤집을 수 없다. 따라서, 크기가 3*3보다 작은 행렬은 뒤집을 필요 없이 비교해주고 다르다면 -1, 같다면 0(line 29~ line 39)이다.

 

이번엔 3*3보다 큰 행렬의 경우를 살펴보자.

우선 행렬 A와 행렬 B의 원활한 비교를 위해 각 좌표의 값이 다르다면 1, 같다면 0이라고 표시하자(line 17 ~ line 26). 목표는 같게 만들어 주는 것이므로 1을 만나면(line 48) 그 좌표부터 3*3 만큼 뒤집어 주도록 한다(그리디 알고리즘).

 

그러나 이때 예외처리를 해주어야 하는 부분이 있다.

해당 좌표부터 3*3만큼의 크기가 나오지 않는다면 뒤집을 수 없기 때문이다. 해당 좌표는 더이상 뒤집을 수 없기 때문에 이 좌표의 값을 검사하여 1이면 "-1"을 출력하고 종료, 0이라면 pass한다(line 61~ line 66). 아래의 그림을 참고하자.

 

[행렬 A를 행렬 B로 만들 수 없는 경우]

 

그 외에 뒤집을 수 있다면, 뒤집는 횟수를 count 해주고, 적절한 결과를 출력할 수 있도록 해준다. 끝!

 

 

Code

#include <stdio.h>
 
int arr[50][50];
 
int main() {
    int N, M;
    scanf("%d %d", &N, &M);
 
    //행렬 A 입력받기
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++)
            scanf("%1d", &arr[i][j]);
    }
 
    int num;
    //행렬 B 입력받기
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%1d", &num);
 
            //입력받은 값이 행렬 A와 다르다면 1
            if (arr[i][j] != num) arr[i][j] = 1;
            //같다면 0
            else arr[i][j] = 0;
        }
    }
 
    //전체 크기가 3*3이 되지 않는 경우
    if (N < 3 || M < 3) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j]) {
                    printf("-1\n");
                    return 0;
                }
            }
        }
        printf("0\n");
    }
    //전체 크기가 3*3보다 큰 경우
    else {
        int cnt = 0;
 
        //전체 범위 검사
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                //다른부분일 때,
                if (arr[i][j]) {
                    //3*3 범위내라면 뒤집기
                    if (i < N - 2 && j < M - 2) {
                        //3*3크기
                        for (int x = i; x < i + 3; x++) {
                            for (int y = j; y < j + 3; y++) {
                                arr[x][y] = !arr[x][y];
                            }
                        }
                        //횟수 count
                        cnt++;
                    }
                    //범위 밖이라면 더이상 뒤집을 수 없음
                    else {
                        if (arr[i][j]) {
                            printf("-1\n");
                            return 0;
                        }
                    }
                }
            }
        }
        //결과 출력
        printf("%d\n", cnt);
    }
    
 
    return 0;
}