[백준 1080] 행렬

www.acmicpc.net/problem/1080

1080번: 행렬

그리디 알고리즘이라는데 그리디는 알다가도 모르겠다..

 

연산 방식은 

1. 두 개의 행렬이 같으면 1 다르면 0으로 표시

2. 1의 행렬에 대해 3*3 뒤집기 연산을 수행

2-1. 연산을 수행할 때 마다 모든 행렬 값이 0이 되는지 확인

2-2. 모든 행렬이 0이라면 연산 횟수 리턴

2-3. 그렇지 않다면 다음 연산 수행

 

먼저 두 행렬을 비교하여 check배열을 만들고 다른 원소 수를 센다.

for (int i = 0; i < n; i++)
  {
    char tmp[51];
    scanf("%s", tmp);
    for (int j = 0; j < m; j++)
    {
      int num = tmp[j] - '0';
      if (num != a[i][j])
      {
        check[i][j] = 1;
        dif++;
      }
    }
  }

 

check배열을 돌면서 연산을 진행한다. 범위가 벗어나는 구역에서 3*3 연산은 불가하므로 i+2<=n-1 즉, i+3<=n까지만 연산한다.

연산할때마다 dif를 카운트해서 dif가 0이 되면 더이상 연산을 진행하지 않는다.

void reverse(int row, int col)
{
  for (int i = 0; i < 3; i++)
  {
    for (int j = 0; j < 3; j++)
    {
      check[row + i][col + j] = !check[row + i][col + j];
      if (check[row + i][col + j] == 0)
      {
        dif--;
      }
      else
      {
        dif++;
      }
    }
  }
}

마지막에 주의해야할 점이 있는데 바로 가로 세로가 3보다 작아서 연산이 수행 불가능한 경우이다.

이 경우엔 무조건 -1이 아니라 diff가 0이면 결과값다 0이므로 주의해야 한다.

#include <stdio.h>

using namespace std;
int n, m, dif;
int a[50][50];
int check[50][50];

void reverse(int row, int col)
{
  for (int i = 0; i < 3; i++)
  {
    for (int j = 0; j < 3; j++)
    {
      check[row + i][col + j] = !check[row + i][col + j];
      if (check[row + i][col + j] == 0)
      {
        dif--;
      }
      else
      {
        dif++;
      }
    }
  }
}

int main(void)
{
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++)
  {
    char tmp[51];
    scanf("%s", tmp);
    for (int j = 0; j < m; j++)
    {
      a[i][j] = tmp[j] - '0';
    }
  }
  for (int i = 0; i < n; i++)
  {
    char tmp[51];
    scanf("%s", tmp);
    for (int j = 0; j < m; j++)
    {
      int num = tmp[j] - '0';
      if (num != a[i][j])
      {
        check[i][j] = 1;
        dif++;
      }
    }
  }
  int res = 0;
  for (int i = 0; i + 3 <= n; i++)
  {
    for (int j = 0; j + 3 <= m; j++)
    {
      if (check[i][j] == 0)
        continue;

      reverse(i, j);
      res++;

      if (dif == 0)
      {
        printf("%d\n", res);
        return 0;
      }
    }
  }

  if (dif == 0)
  {
    printf("%d\n", res);
  }
  else
  {
    printf("-1\n");
  }
  return 0;
}