백준 22352 (C++) 항체 인식

최초 업로드: 2025-03-31 00:00:54

최근 수정 시간: 2025-07-25 10:06:20

게시자: rlatjwls3333

카테고리: 백준

# [Gold V] 항체 인식

[문제 링크](https://www.acmicpc.net/problem/22352)

## 문제 설명

<p>VUNO는 빅데이터와 딥러닝 기술을 통해 학습한 인공지능을 이용해 의학 전문가들의 판단에 도움을 주는 Medical AI 솔루션을 개발하는 전문 기업이다.</p>

<p>VUNO는 최근 SP라는 강력한 새로운 촬영 기법을 개발했다. 이 기법을 사용하면 인체 조직이 격자 형태로 표현되고, 격자의 각 칸에는 해당 부분의 각종 분석 결과를 압축한 하나의 데이터 값이 부여된다. VUNO는 이 SP 촬영 기법을 사용해 CPCU-1202라는 새로운 항체를 연구하려고 한다.</p>

<p>조직에 CPCU-1202 백신을 놓으면, 격자의 칸 중 하나에 항체가 생성된다. 이 항체는 현재 속해 있는 칸과 같은 데이터 값을 가지면서 상하좌우로 인접한 칸이 있을 경우 그 칸으로 퍼져나간다. 이 과정을 계속 반복하다가 항체가 더 이상 퍼져나갈 수 없게 되면, 항체는 조직에 완전히 스며든다. 그 결과로, 항체가 퍼졌던 칸들의 데이터 값은 모두 어떤 동일한 값으로 새로 업데이트된다. 이때, 우연히 원래의 데이터 값과 업데이트된 데이터 값이 동일할 수도 있다.</p>

<p>VUNO의 연구 데이터는 하나의 조직에 백신을 놓기 전의 촬영 결과와 백신을 놓은 뒤의 촬영 결과가 한 쌍으로 이루어져 있다. 두 장의 촬영 결과가 주어질 때, 이 조직에 놓은 백신이 CPCU-1202 백신일 가능성이 있는지 판단하는 프로그램을 작성하라.</p>

## 입력

## 출력

## 풀이
#### 만약 두 촬영 결과가 일치하면, 임의의 위치에 백신을 맞아 같은 값으로 변한 경우일 것입니다.
#### 만약 두 촬영 결과가 다르다면, 백신을 놓기 전의 촬영 결과에서 결과가 다른 임의의 한 위치에 백신을 직접 놓은 뒤에, 그 결과가 입력으로 들어온 백신을 놓은 후의 결과와 같은지 확인하면 됩니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int n, m;
int before[30][30], after[30][30];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
bool visited[30][30];

struct pos {
    int x, y;
};

bool chk(pos start) {
    if(start.x==-1) return true;

queue<pos> q; q.push(start);
    int startBefore = before[start.x][start.y];
    int startAfter = after[start.x][start.y];
    visited[start.x][start.y]=true;
    before[start.x][start.y]=startAfter;
    while(!q.empty()) {
        pos cur = q.front(); q.pop();
        for(int i=0;i<4;i++) {
            int nx = cur.x+dx[i];
            int ny = cur.y+dy[i];
            if(nx<0 || nx>=n || ny<0 || ny>=m || startBefore!=before[nx][ny] || visited[nx][ny]) continue;
            visited[nx][ny]=true;
            before[nx][ny]=startAfter;
            q.push({nx, ny});
        }
    }

for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            if(before[i][j]!=after[i][j]) return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            cin >> before[i][j];
        }
    }
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            cin >> after[i][j];
        }
    }

pos start = {-1, -1};
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            if(before[i][j]!=after[i][j]) {
                start = {i, j};
            }
        }
    }
    if(chk(start)) cout << "YES";
    else cout << "NO";
}
```