백준 17142 연구소3 C++

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

17142번: 연구소 3

연구소에 바이러스가 포진되어 있을 때 바이러스가 전체에 퍼지는데 걸리는 시간의 최솟값을 구하는 문제입니다. 전체 맵의 최대 크기는 50*50 이지만 문제 조건에 바이러스 최대 개수가 10개라 하였으므로 활성바이러스 10C5가지의 경우가 최대 경우의 수입니다.

 

풀이는 다음과 같습니다.

1. 전체 바이러스 중 활성바이러스를 고른다. (dfs로 조합을 이용해 미리 구해주었습니다.)

2. 활성바이러스를 bfs로 돌려 전체에 퍼트립니다.

이 때 우선순위 큐를 이용해 큐를 해당 위치 도달 시간에 따른 오름차순으로 만들어 도달한 위치는 더 작은 값으로 업데이트될 수 없게 하였습니다.

 

코드는 다음과 같습니다.