Joonas' Note
목록플러드필 (1)
Joonas' Note
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)을 한다. 모든 빈칸을 방문한다면 그 때의 탐색..
알고리즘/문제 풀이
2019. 4. 15. 13:53