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

문제 링크입니다. https://www.acmicpc.net/problem/22352

22352번: 항체 인식

이전과 이후를 비교하는 문제였습니다.

백신을 맞기 전과 후의 MAP을 주고 백신을 맞은 확률이 있는지를 알아보는 문제였습니다.

백신을 한번만 맞을 수 있다는 것이 중요했습니다.

 

이전과 이후의 MAP을 비교해서 다른 곳이 하나 있다면 해당 점에서 4방향 탐색을 시작합니다.

탐색을 완료한 뒤에 두개의 MAP을 비교해서 다른 경우 NO, 같은 경우 YES를 출력해주면 되는 문제였습니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <cmath>
#define P pair<int,int>
#define F first
#define S second

using namespace std;

int N, M;
int before[31][31];
int after[31][31];
int check[31][31];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

bool check_map(){
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            if(before[i][j] != after[i][j]) return false; 
        }
    }
    return true;
}

void bfs(int X, int Y){
    queue<P> q;
    q.push({X,Y});
    int number = before[X][Y];
    before[X][Y] = after[X][Y];
    check[X][Y] = 1;
    while(!q.empty()){
        int x = q.front().F;
        int y = q.front().S;
        q.pop();
        for(int i = 0; i < 4; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(xx >= 1 && xx <= N && yy >= 1 && yy <= M){
                if(check[xx][yy] == 0 && before[xx][yy] == number){
                    check[xx][yy] = 1;
                    before[xx][yy] = after[X][Y];
                    q.push({xx,yy});
                }
            }
        }
    }
}

void solve(){
    bool vaccine = true;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            if(vaccine){
                if(before[i][j] != after[i][j]){
                    bfs(i,j);   
                    vaccine = false;
                }
            }
        }
    }
    if(check_map()) cout << "YES";
    else cout << "NO";
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> before[i][j];
        }
    }
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> after[i][j];
        }
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글 남겨주세요!