백준 22352 - 항체인식

백준 22352 - 항체인식


1. 구상

두 배열이 같으면 무조건 YES
아니면 각 지역의 class를 찾기 위해 dfs를 돌린다.

새로 들어온 배열과 비교해서 딱 한개의 class만 달라져야 YES이므로 dfs를 돌릴 때 각 class별로 좌표를 저장한다.


2. 풀이

dfs를 돌려서 cls 벡터에 각 class별로 좌표를 저장해 놓는다.

e.g. cls[1] = [[0,0]. [0,1], ... ,]
1번 class의 좌표들

새로운 배열과 class별로 비교하여 단 한개의 class에서만 숫자가 다르며 YES, 아니면 NO를 출력한다.


3. 코드

#define _CRT_SECURE_NO_WARNINGS

#define IN freopen("input.txt", "r", stdin)
#define f(i, a, b) for (int i = a; i < b; ++i)
#include <bits/stdc++.h>

using namespace std;

int n, m;
bool flag = true;

int A[32][32];
int B[32][32];

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

bool visited[32][32];
vector<vector<pair<int, int>>> cls;
int cnt_cls = -1;
int cnt_0;
int cnt__1;
int num;

void dfs(int y, int x)
{
   f(i, 0, 4)
   {
      y += dy[i];
      x += dx[i];

      if (y >= 0 && y < n && x >= 0 && x < m && A[y][x] == num && !visited[y][x])
      {
         cls[cnt_cls].push_back(make_pair(y, x));
         visited[y][x] = true;
         dfs(y, x);
      }

      y -= dy[i];
      x -= dx[i];
   }
}

int main()
{
   //IN;
   scanf("%d %d", &n, &m);
   f(i, 0, n)
       f(j, 0, m)
           scanf("%d", &A[i][j]);

   f(i, 0, n)
       f(j, 0, m)
           scanf("%d", &B[i][j]);

   // 두 배열이 동일하면 yes
   f(i, 0, n)
       f(j, 0, m) if (A[i][j] != B[i][j]) flag = false;
   if (flag)
   {
      printf("YES");
      return 0;
   }

   // 두 배열이 다르면 확인 필요
   f(i, 0, n)
   {
      f(j, 0, m)
      {
         if (!visited[i][j])
         {
            num = A[i][j];
            cnt_cls++;
            vector<pair<int, int>> point;
            cls.push_back(point);
            cls[cnt_cls].push_back(make_pair(i, j));
            visited[i][j] = true;
            dfs(i, j);
         }
      }
   }

   // 비교 조져!!
   int flg = 0;
   int new_num = -1;

   f(i, 0, cls.size())
   {
      num = A[cls[i][0].first][cls[i][0].second];
      flg = 0; // 모두 같으면 1, 모두 다르면 -1, 이도저도 아니면 0
      if (A[cls[i][0].first][cls[i][0].second] == B[cls[i][0].first][cls[i][0].second])
         flg = 1;
      else
      {
         flg = -1;
      }

      new_num = B[cls[i][0].first][cls[i][0].second];

      f(j, 0, cls[i].size())
      {
         int y = cls[i][j].first;
         int x = cls[i][j].second;

         if (B[y][x] != new_num)
         {
            flg = 0;
            break;
            //이도저도 아니므로 break;
         }
      }

      if (flg == -1)
      {
         cnt__1++;
      }
      else if (flg == 0)
      {
         cnt_0++;
      }

      // 다른 클래스가 2개 이상이므로 백신아님.
      if (cnt__1 + cnt_0 > 1)
      {
         printf("NO");
         return 0;
      }
   }
   if (cnt__1 == 1 && cnt_0 == 0)
      printf("YES");
   else
      printf("NO");
   return 0;
}