[백준 22352][BFS][C++] 항체 인식

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

22352번: 항체 인식

 

주어진 두 배열에서 같은 숫자로 이어진 구역을 나누고(구역은 상하좌우로 이어져있어야 한다), 두 배열의 모든 구역의 모양이 같아야 하고 숫자가 다른 구역이 1개 이하이면 YES, 구역의 모양이 다르거나 숫자가 다른 구역이 2개 이상이라면 NO를 출력해주는 문제다.

 

문제의 예제와 같이 위와 같은 두 배열이 있다고 하자. 우리는 새로운 구역을 찾을 때마다 모양이 다른지, 이 구역이 두 배열간 숫자가 다르다면 이 구역으로써 숫자가 다른 구역이 2개 이상이 되지 않는지를 확인하여 틀린 경우를 잡아줄 것이다.

 

확인을 위해 먼저 첫 번째 배열의 구역의 크기를 BFS로 구한다. 구역은 같은 숫자로 이루어져 있기 때문에 처음 탐색을 시작하는 좌표, 아래 예시에서는 (0,0)의 숫자와 비교하며 탐색해나가면 된다.

노란색 형광펜으로 칠한 부분이 (0,0)이 포함된 구역으로, 크기는 6이다.

 

두 번째 배열에서도 크기를 구하는데 이 때 탐색조건으로 두 번째 배열의 (0,0) 숫자와 나아갈 좌표의 숫자가 같은가 뿐만 아니라 첫 번째 배열에서의 (0,0) 숫자와 나아갈 좌표의 숫자가 같은지도 확인해주어야한다. 만약 크기로만 비교할 경우 구역 자체의 크기는 같지만 모양이 다른 반례가 생기게 된다.

두 번째 배열도 탐색을 완료하고, 두 배열을 탐색하면서 얻은 구역의 크기가 같다면 구역의 모양이 같다는 것이다. 즉 크기가 다를 땐 NO를 출력해주고 코드를 종료하면 된다.

또, 예제와 같이 최초로 구역의 숫자가 다른 경우엔 체크를 해놨다가 만약 배열을 탐색하던 중 또 다시 구역의 숫자가 다른 경우가 나온다면 그때 또한 NO를 출력해주면 된다.

 

탐색이 끝날 때까지 NO를 출력하지 않았다면 그땐 CPCU-1202 백신일 가능성이 있는 것이니 YES를 출력해주면 된다.

 

#include<iostream>
#include<queue>
using namespace std;

int n,m,beforearr[31][31],afterarr[31][31],cnt=0,dic[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
bool before_visited[31][31], after_visited[31][31];

bool Check(int x, int y){
    int beforecnt = 0, aftercnt = 0;

    queue<pair<int,int> > que;

    que.push(make_pair(x,y));
    before_visited[x][y]=true;
    beforecnt++;
    while(!que.empty()){
        pair<int,int> p = que.front();
        que.pop();
        int nx = p.first, ny = p.second;
        for(int i=0; i<4; i++){
            int nex = nx+dic[i][0], ney = ny+dic[i][1];
            if(nex<0 || ney<0 || nex>=n || ney>=m || before_visited[nex][ney] || beforearr[x][y]!=beforearr[nex][ney]){
                continue;
            }
            beforecnt++;
            que.push(make_pair(nex,ney));
            before_visited[nex][ney]=true;
        }
    }

    que.push(make_pair(x,y));
    after_visited[x][y]=true;
    aftercnt++;
    while(!que.empty()){
        pair<int,int> p = que.front();
        que.pop();
        int nx = p.first, ny = p.second;
        for(int i=0; i<4; i++){
            int nex = nx+dic[i][0], ney = ny+dic[i][1];
            if(nex<0 || ney<0 || nex>=n || ney>=m || after_visited[nex][ney] || beforearr[x][y]!=beforearr[nex][ney] || afterarr[x][y]!=afterarr[nex][ney]){
                continue;
            }
            aftercnt++;
            que.push(make_pair(nex,ney));
            after_visited[nex][ney]=true;
        }
    }
    return beforecnt == aftercnt;
}

int main(){
    cin>>n>>m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin>>beforearr[i][j];
        }
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin>>afterarr[i][j];
        }
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(!before_visited[i][j]){
                if(!Check(i,j)){
                    cout<<"NO"<<endl;
                    return 0;
                }
                else{
                    if(beforearr[i][j]!=afterarr[i][j]){
                        cnt++;
                    }
                    if(cnt>1){
                        cout<<"NO"<<endl;
                        return 0;
                    }
                }
            }
        }
    }
    cout<<"YES"<<endl;
}