[백준/C++] 22352 항체 인식

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

코드

#include <iostream>
#include <queue>
using namespace std;

#define MAX 31
#define FASTIO ios::sync_with_stdio(false); cin.tie(NULL);
typedef pair<int, int> pi;
int n, m;
int before[MAX][MAX], after[MAX][MAX];
int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };

void bfs(int x, int y) {
	queue<pi> q;
	q.push({ x, y });
	int now = before[x][y];
	int changed = after[x][y];

	while (!q.empty()) {
		int nx = q.front().first;
		int ny = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int gx = nx + dx[i];
			int gy = ny + dy[i];

			if (gx >= 0 && gx < n && gy >= 0 && gy < m) {
				if (before[gx][gy] == now) {
					before[gx][gy] = changed;
					q.push({ gx, gy });
				}
			}
		}
	}
}

int main() {
	FASTIO;

	cin >> n >> m;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < m; j++)
			cin >> before[i][j];

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> after[i][j];

	bool flag = false;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!flag && before[i][j] != after[i][j]) {
				bfs(i, j);
				before[i][j] = after[i][j];
				flag = true;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (before[i][j] != after[i][j]) {
				cout << "NO";
				return 0;
			}
		}
	}
	cout << "YES";
	return 0;
}

설명

before와 after를 비교해서 값이 다르다면 해당 지점에서 백신을 놓았을 가능성이 있습니다. 백신은 한 번만 주입할 수 있으므로 처음으로 다른 지점을 만나면 해당 지점에서부터 bfs를 돌리면서 값이 같은 지점을 전부 after[i][j] 값과 동일하게 변경해줍니다. 

 

마지막에 2중 for문으로 값을 비교해주는데, 다른 값이 나오면 백신 처리를 하지 않은 것이니 NO를 출력합니다. 두 배열의 값이 모두 동일하면 YES를 출력합니다.

 

느낀 점

BFS를 이용해서 풀었습니다.