💛IV [백준 14502/C++] 연구소

BOJ 문제 보기

1. 문제

1. 크기가 $N \times M$인 직사각형
2. 빈 칸, 벽으로 구성
3. 바이러스는 상하좌우로 인접한 빈 칸으로 확산
   • 0 : 빈 칸, 1 : 벽, 2 : 바이러스
4. 반드시 벽 3개 생성할 것
5. 안전 영역 크기의 최댓값 계산

BFS와 DFS로 해결할 수 있다. 두 탐색 알고리즘이 방문한 정점이 바이러스의 확산 영역이 된다.

알고리즘이 방문하지 않은 정점을 계산해 안전 영역 크기를 구해보자.

---

2. 풀이 과정

바이러스의 위치를 모두 큐에 넣어 확산 초기값을 지정하고 bfs 알고리즘을 활용해 빈 칸을 2로 바꾸어준다.

큐가 비었다면 빈 칸의 개수를 세어 안전 영역 크기를 출력한다.

벽을 세우기 위해 반복문을 3번 중첩시켜 벽 위치 (x1, y1), (x2, y2), (x3, y3)별 빈 칸의 개수를 모두 구하고 최댓값을 반환한다.

지도의 크기가 최대 $8 \times 8$이므로 벽을 세 개 설치하는 경우와 bfs 탐색 경우의 수를 모두 합해 총 $O((NM)^{4})$만큼의 시간이 걸린다.