[C++][백준 BOJ]1080_행렬.

문제 번호

https://www.acmicpc.net/problem/1080

1080번: 행렬

 

알고리즘 분류

 그리디(greedy).

 

 

문제 풀이

 문제에서 주어진 A,B 행렬을 (0,0) 부터 (N-2, M-2) 까지 탐색하여서 서로 다른 값을 갖을때 마다 3*3 크기의 부분행렬을 뒤집어주는 과정을 수행하였다.

 

1. 다른 부분이 있을때 까지 탐색한다.

for (int i = 0; i < N - 2; i++)
    {
        for (int j = 0; j < M - 2; j++)
        {
            if (arry1[i][j] != arry2[i][j])
            {
                change(arry1, i, j);
                answer++;
            }
        }
    }

2. 다른 부분을 발견하면 3*3 크기의 부분행렬을 뒤집어준다.

void change(char arry1[][MAX], int y, int x)
{
    for (int i = y; i < y + 3; i++)
    {
        for (int j = x; j < x + 3; j++)
        {
            if (arry1[i][j] == '1')
                arry1[i][j] = '0';
            else if (arry1[i][j] == '0')
                arry1[i][j] = '1';
        }
    }
}

전체코드

#include <iostream>
using namespace std;

#define MAX 50

char arry1[MAX][MAX];
char arry2[MAX][MAX];

void Insert(int N, int M)
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            char num;
            cin >> num;
            arry1[i][j] = num;
        }
    }

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            char num;
            cin >> num;
            arry2[i][j] = num;
        }
    }
}

void change(char arry1[][MAX], int y, int x)
{
    for (int i = y; i < y + 3; i++)
    {
        for (int j = x; j < x + 3; j++)
        {
            if (arry1[i][j] == '1')
                arry1[i][j] = '0';
            else if (arry1[i][j] == '0')
                arry1[i][j] = '1';
        }
    }
}

int Solution(int N, int M)
{
    int answer = 0;

    for (int i = 0; i < N - 2; i++)
    {
        for (int j = 0; j < M - 2; j++)
        {
            if (arry1[i][j] != arry2[i][j])
            {
                change(arry1, i, j);
                answer++;
            }
        }
    }

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            if(arry1[i][j] != arry2[i][j])
                return -1;
        }
    }

    
    return answer;
}

int main()
{
    int N, M;
    cin >> N >> M;
    Insert(N, M);
    cout << Solution(N, M) << '\n';

    return 0;
}

특이사항

 떠오르는 아이디어가 이거말곤 없어서 일단 진행하였는데 다행이 정답이였다.