BOJ 22352: 항체 인식

#BOJ 22352: 항체 인식

22352번: 항체 인식

#풀이

문제를 보자마자 내가 좋아하는 BFS문제라는 것을 알았다. 일단 시약을 뿌리면 숫자가 같은 구역만 시약의 효과를 볼 수 있다.

 

입력으로 처음 상태와 후의 상태를 주는데

 

처음 상태에서 어느 한 구역을 선택하여 bfs를 한번 하고 나면 후에 상태와 똑같으면 시약을 뿌린 것이고 아니면 뿌리지 않은 것이다.

 

그래서 각각 처음과 나중 상태를 비교하여 둘의 값이 다른 곳을 bfs의 시작지점을 두고 bfs 한번 돌았을 때의 상태와 나중 상태가 똑같아야 한다.

 

#풀이

 

#include<bits/stdc++.h>

using namespace std;
int arr[31][31];
int arr2[31][31];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin>>n>>m;
	for(int i = 1; i <=n; i++){
		for(int j = 1; j <=m; j++){
			cin>>arr[i][j];
		}
	}
	for(int i = 1; i <=n; i++){
		for(int j = 1; j <=m; j++){
			cin>>arr2[i][j];
		}
	}
	int vis[31][31] = {0,};	
	queue<pair<int, int>> q;
	for(int i = 1; i <=n; i++){
		bool flag = 0; // 시약을 한번 뿌리면 bfs한번만 함
		for(int j = 1; j <=m; j++){
			if(arr[i][j] == arr2[i][j] || vis[i][j] !=0) continue;
			
			flag = 1;
			int pre = arr[i][j];
			arr[i][j] = arr2[i][j];
			q.push({i,j});
			vis[i][j] = 1;
			
			while(!q.empty()){
				auto nxt = q.front(); q.pop();
				
				for(int d = 0; d <4; d++){
					int x = dx[d] + nxt.first;
					int y = dy[d] + nxt.second;
					
					if(x < 1 || y < 1 || x > n || y > m|| vis[x][y] != 0||
					arr[x][y] != pre) continue;
					
					arr[x][y] = arr[i][j];
					vis[x][y] = 1;
					q.push({x,y});
				}
			}
			break;
		}
		if(flag)
			break;
	}
	

	for(int i = 1; i <=n; i++){
		for(int j = 1; j<=m; j++){
			if(arr[i][j] != arr2[i][j]){
				cout << "NO" << '\n';
				return 0;
			}
						
		}
	}
	
	
	cout << "YES"<<'\n';
	
	return 0;
}