BOJ - 14502) 연구소

< BOJ 14502 연구소 >

벽 3개를 세워 바이러스가 퍼지지 않은 안전 구역을 최대화해야 하는 문제로, BFS 및 재귀 함수의 사용이 필요하다. 문제 해결의 기본 개념은, 재귀 함수를 이용하여 0 으로 표시된 모든 부분에 대하여 벽을 세우는 것을 고려하고, BFS 를 통하여 바이러스가 퍼진 후의 데이터에서 안전영역의 수를 도출하여 지속적으로 비교하는 것이다. 

 

기존의 입력값, 임의의 벽을 세운후의 새로운 배열, 벽을 세운 배열에서 바이러스가 퍼지고 난 다음의 배열의 총 3가지 배열이 사용되어야 한다. 

BFS 개념을 사용하기 위하여 큐를 선언한다. 벽이 세워진 후 복제된 배열인 replica 의 정보를 바이러스가 퍼진후의 데이터를 도출하기 위해 spread 행렬에 대입하고, queue 에 바이러스의 위치를 넣는다. 이후, BFS 의 기본 형태에 따라 큐가 완전히 비워질 때 까지 while 문을 반복하여 바이러스가 퍼진후의 배열을 도출하고, 이후 안전영역의 개수를 구하고 max 함수를 사용하여 최고값을 갱신한다.

재귀함수를 사용하여, 복제 배열 내부에 벽이 3개 세워질 때 까지 함수를 반복하고 벽이 3개 세워졌다면 BFS 함수를 실행시킨다.