[그래프] 항체 인식(22352)(C++)

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

22352번: 항체 인식

 

1. 문제 개요

 

조직에 CPCU-1202 백신을 놓으면, 격자의 칸 중 하나에 항체가 생성된다. 이 항체는 현재 속해 있는 칸과 같은 데이터 값을 가지면서 상하좌우로 인접한 칸이 있을 경우 그 칸으로 퍼져나간다. 이 과정을 계속 반복하다가 항체가 더 이상 퍼져나갈 수 없게 되면, 항체는 조직에 완전히 스며든다. 그 결과로, 항체가 퍼졌던 칸들의 데이터 값은 모두 어떤 동일한 값으로 새로 업데이트된다. 이때, 우연히 원래의 데이터 값과 업데이트된 데이터 값이 동일할 수도 있다.

VUNO의 연구 데이터는 하나의 조직에 백신을 놓기 전의 촬영 결과와 백신을 놓은 뒤의 촬영 결과가 한 쌍으로 이루어져 있다. 두 장의 촬영 결과가 주어질 때, 이 조직에 놓은 백신이 CPCU-1202 백신일 가능성이 있는지 판단하는 프로그램을 작성하라.

 

 

2. 입출력

 

 

 

3. 문제 풀이

 

문제를 제대로 읽는 게 조금 힘들지만 막상 풀이는 쉬운 문제.

항체를 맞기 전의 사진과 맞은 후의 사진을 입력 받은 후, 달라진 한 개의 블록이 있다면 그 블록을 시작점으로 저장한다.

그 다음에 시작점부터 BFS를 통해 같은 값을 가지는 블록들을 탐색하며 바꿔준다.

BFS를 마치고 난 후에, 항체를 맞기 전의 결과와 맞은 후의 결과를 비교하여 같다면 그것은 CPCU-1202 백신을 맞은 결과이고, 다르다면 CPCU-1202 백신을 맞은 결과가 아니다.

 

 

4. 전체 코드