[백준] 17141번: 연구소2

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

풀이

1.

입력으로 주어진 바이러스를 놓을 특정위치 중에 내가 놓을곳 m개를 골라야 한다.

나는 입력을 받으면서 따로 pair<int, int> place[10]배열에 바이러스를 놓을 좌표를 저장해두었다.

DFS로 place배열의 인덱스를 가지고 그 중에 m개의 장소를 골랐다.

 

2.

m개의 장소를 고르고 나면 그 부분을 출발점으로 두어야한다.

vis[x][y]는 0으로 두고 큐에 넣는다. (vis배열은 -1로 초기화되어있고, 퍼져나가는 시간을 저장해둘것이다.)

m개의 장소에 대해 큐에 모두 넣고 BFS를 시작한다.

 

3.

BFS는 아직 방문하지 않았고(vis == -1), 맵이 0이거나 2인 부분을 방문한다.

 

4.

BFS로 vis배열을 모두 채우고, 이중for문으로 vis배열을 훑으면서 걸린시간을 체크한다.

만약에 맵이 0인데 vis에서 -1로 되어있으면 바이러스가 퍼지지 못한 것이므로 -1을 리턴해야한다.

그렇지 않다면 vis배열에서 제일 큰값을 min_time으로 설정한다

 

5.

DFS에서 m개를 고를때마다 2~4번을 진행하고 결과로 ans에 제일 작은값을 갱신한다!

ans의 초기값은 987654321(걍 큰수)이다. 결과가 -1이 아닌 경우에만 ans를 작은 값으로 갱신한다.

나중에 출력할때 ans가 987654321면 -1을 출력하고, 아니면 ans를 출력하면 끄읕!

 

코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/17141.cpp

결과