백준 17142번 - 연구소 3
https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 필요한 배경지식 DFS, BFS 문제 해결 방법 모든 빈칸에 바이러스가 있게 되는 최소 시간을 구해야 합니다. DFS를 이용하여 활성화할 M개의 바이러스를 고르고, 해당 바이러스들을 시작노드로 BFS를 수행하여 최소 시간을 구해낼 수 있습니다. 바이러스가 총 k개 있고 m개의 바이러스를 활성화 시킬 수 있다면 C(k,m) 만큼 BFS를 수행하여 최소 시간을 구해야 합니다. 최소시간을 구하는 과정에서 바이러..
알고리즘 공부/문제풀이
2021. 5. 31. 14:28
반응형