BOJ 17142 - 연구소 3

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

문제

연구소에 이미 존재하는 바이러스들 중 \(m~(2\le m \le 10)\)개를 활성 상태로 바꾸어 바이러스를 퍼뜨리는 문제이다. 그 때, 연구소의 모든 빈칸에 바이러스가 퍼지게 하는 최소 시간을 구해야 한다.

풀이

연구소에 존재하는 바이러스 들 중 \(m\)개를 골라야한다. DFS 같은 방법으로 고를 수 있지만, next_permutation을 사용하면 간단하다.
4개 중 2개를 고르는 조합은 0011 → 0101 → 0110 → 1001 → 1010 → 1100 순으로 진행된다.

이런 특징을 사용하여 매번 적당히 \(m\)개를 선택하여 플러드 필(Flood Fill, BFS)을 한다.

모든 빈칸을 방문한다면 그 때의 탐색 시간을, 그렇지 못한다면 \(\infty\)을 반환하면서 모든 조합을 확인하여 최소 시간을 구한다. \(m\)개 중 2의 개수(\(\le 10\))를 고르는 조합의 수만큼 반복된다.

시간복잡도는 \(O({}_{10}C_m \cdot N^2)\)

코드