[BOJ] 14502번 연구소 (C++)

문제 링크 (https://www.acmicpc.net/problem/14502)

14502번: 연구소

0: 빈칸 / 1: 벽 / 2: 바이러스

입력받은 직사각형 중에서 0인 부분은 바이러스가 퍼질 수 있는 지역이다. 바이러스가 최대한 퍼지지 않도록 벽을 세워야 하는데 세울 수 있는 벽의 개수는 무조건 3개이다. 벽을 세울 수 있는 곳들 중 3곳을 골라 벽을 세웠을 때 얻을 수 있는 안전 영역의 크기의 최댓값을 구하는 문제!

 

1. 바이러스(2) 좌표, 빈 칸(0) 좌표를 모두 vector에 기억해놓음

2. false로 초기화된 bool형 vector를 생성 (bool형 vector의 크기 = 빈 칸 좌표의 개수)

3. bool형 vector중 3개만 true로 설정하고 next_permutation (벽이 3개이므로)

4. 조합이 완성되면 true인 위치에 벽 설치

5. 바이러스 위치에서 bfs 시작

6. 안전 영역(0) 수를 count => 최댓값 기억

---

[소스코드]

---

2021-10-07

Gold 5

알고리즘 분류

- 그래프 이론

- 그래프 탐색

- 브루트포스 알고리즘

- 너비 우선 탐색