[BOJ] 백준 17142. 연구소 3

▶문제설명

[BOJ] 백준 17142. 연구소 3

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

▶Hint

---

브루트 포스 & BFS & 시뮬레이션 문제이다.

M개의 바이러스를 활성화 시켜서 활성/비활성 바이러스로 가득 채우기 위해 걸리는 최소 시간을 구하는 문제다.

모든 바이러스가 활성화 되어 있지 않아도 괜찮다는 조건이 문제를 까다롭게 만드는 것 같다.

가능한 모든 경우에 대해 시뮬레이션 해야 하므로, 기존의 map을 복사하여 활용한다.

벽은 -1, 바이러스는 -2, 빈 곳은 -3으로 표시하는 것이 핵심이다.

- 입력으로 주어진 바이러스들 중 M개를 선택하는 모든 경우는 어떻게 구할 것인가?

next_permutation()을 활용하면 쉽게 해결할 수 있다.

- 활성/비활성 바이러스로 가득 차는데까지 걸리는 시간은 어떻게 구할 것인가?

1. 선택된 M개의 바이러스를 Queue에 push한다.

2. map의 바이러스가 번식되는 위치에 걸린 시간을 표시해가며 BFS를 수행한다.

3. 표시된 시간 중 최대 값을 취한다.

벽을 1로 저장하고 바이러스를 2로 저장하는 경우 최대 값이 무조건 2 이상이 되므로 원하는 결과를 얻을 수 없다.

BFS 수행 시 다음 좌표의 값이 -2인 경우 해당 좌표에 현재 time을 표시하도록 구현해야 비활성 바이러스까지 고려하여 답을 구할 수 있다.

- 모든 곳을 바이러스로 채울 수 없는 경우는 어떻게 체크할 것인가?

1. map의 바이러스가 번식되는 위치에 걸린 시간을 표시해가며 BFS를 수행한다.

2. BFS 종료 후 map에 -3이 존재한다면 모든 곳을 바이러스로 채울 수 없다는 의미이다.

빈 곳을 0으로 저장하는 경우 빈 곳과 처음 활성화 시킨 바이러스를 구분할 수 없다.

▶Solution