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

문제

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

22352번: 항체 인식

풀이

두 배열(before와 after)을 (0, 0)부터 한 칸씩 비교하면서, 값이 다를 때 BFS를 실행해서 before배열의 값을 after배열의 값으로 바꿔준다. 

이렇게 BFS를 돌리고 나서도 두 배열에 값이 다른 칸이 있다면, NO이고 아니면 YES이다. 

 

여기서 주의해야 할 점은, BFS를 "딱 한 번" 돌려야 한다는 것이다. 

아래 예시를 보면 쉽게 이해할 수 있다. 아래 예시의 답은 NO이다. 두 배열은 구역은 동일하게 나뉘어져 있지만, 구역을 채우고 있는 숫자가 다른 부분이 두 군데이기 때문이다. 이런 경우에 BFS를 여러번 돌리게 한다면 두 배열에 대한 결과는 YES가 나오게 된다. 따라서 BFS를 한 번만 돌리도록 처리를 해주어야 한다. 

2 2 2 1        3 3 3 1

2 2 1 2        3 3 1 3

2 1 2 2        3 1 3 3 

1 2 2 2        1 3 3 3

  

코드

#include <iostream>
#include <queue>

using namespace std;

int before[31][31];
int after[31][31];
bool visited[31][31];
int N, M;

int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };

void BFS(int r, int c, int num, int target) {
	visited[r][c] = 1;
	queue<pair<int, int>> q;
	q.push({ r, c });
	while (!q.empty()) {
		int tempR = q.front().first;
		int tempC = q.front().second;
		q.pop();
		before[tempR][tempC] = target;
		for (int i = 0; i < 4; i++) {
			int nextR = tempR + dr[i];
			int nextC = tempC + dc[i];
			if (nextR < 0 || nextR >= N || nextC < 0 || nextC >= M) continue;
			if (!visited[nextR][nextC] && before[nextR][nextC] == num) {
				visited[nextR][nextC] = 1;
				q.push({ nextR, nextC });
			}
		}
	}
}

int main() {
	cin >> N >> M;
	for (int n = 0;n < N;n++) {
		for (int m = 0;m < M;m++) {
			cin >> before[n][m];
		}
	}
	for (int n = 0;n < N;n++) {
		for (int m = 0;m < M;m++) {
			cin >> after[n][m];
		}
	}
	bool flag = 1; //BFS를 딱 한번만 돌리기 위함 
	for (int n = 0;n < N;n++) {
		for (int m = 0;m < M;m++) {
			if (before[n][m] != after[n][m] && flag) {
				BFS(n, m, before[n][m], after[n][m]);
				flag = 0;
			}
		}
	}
	bool result = 1;
	// 검사
	for (int n = 0; n < N; n++) {
		for (int m = 0; m < M; m++)
			if (before[n][m] != after[n][m])
				result = 0;
	}
	if (result) cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}

결과