백준 - 연구소2

문제 출처: https://www.acmicpc.net/problem/17141

17141번: 연구소 2

 

 

2의 값을 가지는 좌표 중에 M개에 바이러스가 들어갈 수 있다.

4방 모두 동시에 퍼지므로 BFS!

 

조합을 통해 바이러스가 들어갈 공간을 구하고!

그 공간만 큐에 넣고 BFS돌려야하나??

 

 

초기 의사 코드

1. 좌표 값이 2 인 부분은 다 리스트에 넣는다.
2. 조합을 통해 M개를 구한다.
3. M개가 구해지면  새로운 지도를 만들고, 큐에 해당 M개의 좌표를 넣고 두 개를 BFS로 보낸다.
4. BFS 돌릴 때마다 최솟값 구한다.

 

 

수정된 의사 코드

1. 좌표 값이 2인 부분은 다 리스트에 넣는다.
2. 좌표가 0 인 경우가 없는 경우, 확산이 이미 최대이므로 정답은 0이다.
3. 조합을 통해 M개를 구한다.
4. M개가 구해지면 새로운 지도를 만들고, 큐에 해당 M개의 좌표를 넣고 두 개를 BFS로 보낸다.
5. M개의 좌표에 해당되지 않는 2는 0으로 해준다(BFS에서 방문 가능하게)
6. BFS 돌릴 때마다 최솟값 구한다.
7. 새로 배열을 복사하는 것이므로 방문 배열을 필요 없다.
8. Que 안에서도 size만큼 또 돌아야 하는데 그 이유는 M개가 동시에 확산하기 때문이다(size만큼 돌고 나서 time을 ++해준다.)
9. time보다 ans가 작으면, 이전에 구한 확산 속도보다 더 오래 걸린다는 것을 의미하므로 중간에 멈춰도 된다.(다시 조합으로 돌아와 새로운 조합을 구한다.)