백준 22352 항체 인식 c++ [컴공과고씨]

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

22352번: 항체 인식

문제를 읽고 bfs를 떠올렸다.

 

아이디어

백신 놓기 전과 결과를 비교한다. 여기서 만약 다른게 나오면 bfs를 돌려서 숫자를 결과의 값으로 바꾸어 주고 백신은 한번만 놓을 수 있기 때문에 비교를 멈춘다. 그 후 바뀐 값과 주어진 결과를 비교해서 하나라도 다른 값이 있다면 no를 다 똑같다면 yes를 출력해주면 된다.

 

 

단계별 풀이

1. 입력값 받을 두 개의 배열 선언

2. 두 값을 비교함

3. 다른 값이 나왔을 경우 bfs를 돌림

4. bfs는 상하좌우로 움직이면서 만약 값이 놓기전 값과 같은 경우 놓은 후 값으로 바꾸어준다.

5. bfs로 바뀐 값과 주어진 결과와 비교하면 다른 값이 있다면 no를 출력한다.

 

 

전체코드

#include <iostream>
#include <queue>
using namespace std;
int bef[32][32];
int aft[32][32];
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
int n, m;
 
void bfs(int a,int b,int bf, int af){
    queue<pair<int, int>> q;
    q.push(make_pair(a, b));
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4;i++){ //상하좌우로 움직임
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if(nx < m && nx >=0 && ny <n && ny >=0){              
                if(bef[ny][nx] == bf){ // 바뀌어야할 값이면
                    bef[ny][nx] = af; // 결과 값으로 바꾸어 줌
                    q.push(make_pair(nx, ny)); 
                }
            }
        }
    }
}
 
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    
    for (int i = 0; i < n;i++){
        for (int j = 0; j < m;j++){
            cin >> bef[i][j]; //놓기 전 값
        }
    }
    for (int i = 0; i < n;i++){
        for (int j = 0; j < m;j++){
            cin >> aft[i][j]; // 놓은 후 값
        }
    }
    bool injected = false;
    for (int i = 0; i < n;i++){
        for (int j = 0; j < m;j++){
            if(!injected){ // 백신은 한번만 놓을 수 있음
                if(bef[i][j] != aft[i][j]){
                    bfs(j, i, bef[i][j], aft[i][j]);
                    bef[i][j] = aft[i][j]; // 첫 시작 값 바꾸어줌
                    injected = true;
                }
            }
        }
    }    
    for (int i = 0; i < n;i++){
        for (int j = 0; j < m;j++){
            if(bef[i][j] != aft[i][j]){ // 하나라도 다르면 NO
                cout << "NO"; 
                return 0;
            }
        }
    }
    cout << "YES";
    return 0;
} //25min

체감난이도	걸린시간	참고	사용 알고리즘
하	25min	x	BFS(브루트 포스)