BOJ/백준 22352 항체 인식

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

22352번: 항체 인식

언어 : C++17

환경 : VSCode gcc 8.1.0

 

아이디어

BFS를 활용하여 해결할 수 있을 거 같아서 BFS를 사용해서 해결했다
처음에는 모든 점에 대해서 BFS를 할까 생각했으나 잘 생각해보니 서로 다른 값을 가진 한 개의 인덱스에서 BFS를

돌린 후 배열이 같지 않다면 백신일 가능성이 없으니 서로 다른 값을 가진 한 개의 인덱스에 대해서만 BFS를 했다.

 

코드

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int arr[100][100];
int vis[100][100];
int after[100][100];
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

bool __cmp(int n, int m){ // 배열을 비교
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(arr[i][j] != after[i][j]) return false;
        }
    }
    return true;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> arr[i][j];
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> after[i][j];
        }
    }
    bool inject = false; // BFS를 돌린적이 있는지 없는지 판별하는 변수
    for(int i = 0; i < n; i++){
    	if(inject) break; // 한번 주사 했으면 더 이상 주사 할 필요가 없음
        for(int j = 0; j < m; j++){
            if(vis[i][j] || arr[i][j] == after[i][j]) continue;
            // 두 배열이 같거나 이미 방문한 적이 있으면 continue
            inject = true; // BFS를 돌렸다고(주사를 놓았다고) 표시
            queue<pair<int,int>> Q;
            Q.push({i,j});
            int key = arr[i][j]; // 원래 arr[i][j]의 값을 저장
            arr[i][j] = after[i][j];
            vis[i][j] = 1;
            while(!Q.empty()){
                auto cur = Q.front(); Q.pop();
                for(int dir = 0; dir < 4; dir++){
                    int nx = cur.X + dx[dir];
                    int ny = cur.Y + dy[dir];
                    if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                    if(arr[nx][ny] != key || vis[nx][ny]) continue;
                    Q.push({nx,ny});
                    vis[nx][ny] = 1;
                    arr[nx][ny] = after[i][j]; // 원래 arr 인덱스의 값을 바꿔줌
                }
            }
        }
    }
    if(__cmp(n,m)) cout << "YES"; // 같으면
    else cout << "NO"; // 다르면
    return 0;
}

결과