[BOJ/22352] 항체인식, c++

UCPC 2021 예선 예선 B번

🔗 링크

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

22352번: 항체 인식

🤯 한줄 후기

문해력 왤케 낮지?

🤷 문제

👩‍💻 풀이

이번 UCPC 2021 예선 B번 문제이다. 내가 풀었고, 보자마자 쉬워보여서 구현하였는데 1회 WA를 받았다.

틀린 이유는 내가 문제 해석을 완전 잘못해서

 

문제를 간략히 정리하면, 백신을 어느곳에 1회 투입하면 촬영후 사진에서는 투입한 위치와 상-하-좌-우 연결되어 있으면서 같은 값을 가지는 곳은 전부 다 어떤 임의의 값으로 변경되어 보인다. 이때 백신을 투약한 것이 맞는지 아닌지를 판단하는 문제이다.

여기서 나는 1회 투입하는 것을 전혀 이해하지 못하고, 여러번 투입해도 되는 줄 알았다. 여러번 투입하되 변경되는 값이 모두 다른 것으로 이해해서 구현했고, 당연히 WA를 받았다.

 

천천히 문제를 다시 읽어보면서 1회 투입해서 판단하는 것을 이해하고 원래 구현한 코드를 살짝 수정하여 제출해 AC를 받을 수 있었다.

구현은 간단하다. 촬영 전 사진 전체를 비교하되, 촬영 후 사진과 달라진 부분에서만 BFS 를 돌린다. 

BFS를 통해 변경된 값으로 촬영 전 사진 그래프에서 상-하-좌-우를 갱신해주고, 마지막에는 촬영 전 - 촬영 후를 비교해 값이 모두 같다면 백신을 투약한 것으로 보면 된다. 

이 때, 백신 투약후 변경된 값이 이전과 같을 수도 있으므로 처음에 모두 같으면 아예 YES를 출력하도록 예외처리를 해주었다.

N,M 이 30 까지라 이렇게 변경된 부분만 탐색하지 않고 아예 전부 다 탐색해도 충분히 시간 안에 가능하다.

 

사실 내가 풀다 절어서 그렇지 대회 때 체감 난이도는 실버 1~2 정도라 생각했는데 의외로 난이도는 골드5로 잡혀있어서 신기했다.

💻 코드

//AC
//UCPC 2021 예선 B 항체인식
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
using namespace std;
int arr[32][32];
int arr2[32][32];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int visit[32][32];
int N, M;
map<int, int> m;
void bfs(int x, int y, int val, int prev) { 
    queue<pair<int, int>> q;
    q.push({x, y});
    visit[x][y] = true;
    while(!q.empty()) {
        pair<int, int> node = q.front();
        q.pop();
        for(int i=0; i<4; i++) {
            int nx = node.first + dx[i];
            int ny = node.second + dy[i];
            if(nx <0 || ny < 0 || nx >= N || ny >= M)   continue;
            if (prev == arr[nx][ny] && !visit[nx][ny]) {
                arr[nx][ny] = val;
                visit[nx][ny] = 1;
                q.push({nx, ny});
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int ch = 1;
    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 >> arr2[i][j];
            if(arr2[i][j] != arr[i][j]) ch = 0;
        }
    }
    if(ch) { //모두 같음
        cout << "YES";
        return 0;
    }
    int ck = 0;
    for (int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            if(arr[i][j] != arr2[i][j] && !visit[i][j]) {
                int prev = arr[i][j];
                arr[i][j] = arr2[i][j];
                bfs(i, j, arr2[i][j], prev);
                ck = 1; break;  //한번 검사후 종료
            }
        }
        if(ck)  break;
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if(arr[i][j] != arr2[i][j]) {
                cout << "NO";
                return 0;
            }
        }
    }
    cout << "YES";
    return 0;
}