백준[22352] 항체 인식

문제 설명

문제 링크

http://icpc.me/22352

풀이

간단한 bfs/dfs문제이다. 붙어있는 같은 데이터들을 모두 탐색하면서, before와 after가 다른 세트가 2세트 이상 있다면 No를 출력하면 되는 문제다. 필자는 bfs로 구현했다.

코드

#include <cstdio>
#include <queue>

using namespace std;

int before[32][32], after[32][32];
bool visited[32][32];
queue<pair<int, int>> q;
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int main() {
    int n, m; scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &before[i][j]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &after[i][j]);
    bool flag = true;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!visited[i][j]) q.push({i, j});
            if (!q.empty() && before[i][j] != after[i][j]) cnt++; 
            while (!q.empty()) {
                auto [y, x] = q.front();
                q.pop();
                visited[y][x] = true;
                for (int k = 0; k < 4; k++) {
                    int ny = y + dir[k][0], nx = x + dir[k][1];
                    if (ny < 1 || nx < 1 || ny > n || nx > m) continue;
                    if (before[ny][nx] == before[i][j] && !visited[ny][nx]) {
                        q.push({ny, nx});
                        if (after[ny][nx] != after[i][j]) flag = false;
                    }
                }
            }
        }
    }    
    if (flag && cnt < 2) printf("YES");
    else printf("NO");
}