[백준]17142 연구소3 - C++

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

17142번: 연구소 3

문제

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스의 위치이다.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2

M = 3이고, 바이러스를 아래와 같이 활성 상태로 변경한 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 비활성 바이러스는 *, 활성 바이러스는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.

* 6 5 4 - - 2
5 6 - 3 - 0 1
4 - - 2 - 1 2
3 - 2 1 2 2 3
2 2 1 0 1 - -
1 - 2 1 2 3 4
0 - 3 2 3 4 *

시간이 최소가 되는 방법은 아래와 같고, 4초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.

0 1 2 3 - - 2
1 2 - 3 - 0 1
2 - - 2 - 1 2
3 - 2 1 2 2 3
3 2 1 0 1 - -
4 - 2 1 2 3 4
* - 3 2 3 4 *

연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

입력

첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

출력

연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.

---

여러 개의 바이러스 중에서 M개의 바이러스만 선택하여 확장시키는 문제이다.

조합의 경우 재귀 방식을 이용하여 선택을 하거나 하지 않는 방식으로 호출하여 선택한 바이러스가 M개가 될 때 바이러스 시뮬레이션을 돌리면 된다.

바이러스 시뮬레이션은 문제의 예시와 같이 칸 마다 바이러스가 도착한 시간을 둔다(vis 배열).

- 벽의 경우 -1로 설정하고 선정된 바이러스는 0으로 설정한다.

- 큐를 활용하여 전염시켜 나가는데

    - 빈칸을 전염시키면 vis [i][j]를 전염된 시간으로 설정, 전염시킨 빈칸의 수(cnt)를 증가, tick을 빈칸이 전염된 시간으로 갱신한다.

    - 비활성화 바이러스를 활성화 시키면 cnt 나 tick은 갱신하지 않고 큐 삽입과 vis 배열만 갱신한다.

    - 가장 최근에 갱신된 vis 배열의 값이 총 걸린 시간이다.

 

---

     문제에 이차원 배열을 본 순간 BFS 혹은 DFS를 활용하여 풀어야 한다고 생각을 하였고 여러 개의 바이러스 중에서 M 개를 선택한다는 부분에서 조합 + BFS로 문제를 풀 수 있다는 생각을 하였다. 풀이가 길어질 것 같아 먼저 생각을 정리하고 간단한 플로우를 손으로 작성하고 코드를 짰다. 하지만 잘 되지 않았다. 바이러스만 남으면 BFS를 종료해야 된다는 생각에 해당 루프에서 빈칸이 차지 않았다면 종료를 하였으나 바이러스가 차서 더 나아가는 경우를 생각하지 못했다. 그래서 새로운 변수를 더해서 하였지만 그럴 필요가 없이 그냥 일반적인 경우와 같이 q가 비어있을 때까지 돌리면 되는 것이었다. 종료해야 된다는 생각도 반복마다 tick 변수를 증가시켰는데 이는 같은 시간에 전염된 바이러스조차 계속 증가되어 숫자가 너무 커졌다. 따라서 vis 배열을 int로 바꾸고 문제의 예시와 같이 해당 칸에 바이러스가 온 초로 바꾸고 가장 최신 칸을 tick으로 설정하였더니 정답을 받을 수 있었다.

     문제를 보고 풀이를 생각해내고 구현을 하고 디버깅을 했다. 생각을 조금 더 했다면 디버깅 시간을 많이 줄일 수 있었을 것 같다. 그래도 잘 풀어서 한 번에 정답을 맞힐 수 있게 되었다! 요즘 든 생각인데 첫 시도와 다른 시도의 비중이 다른 것 같다. 실제 코딩 테스트에 간다면 틀렸습니다를 알 길이 없기 때문에 최종 제출이 정답이 된다. 실전처럼 첫 제출을 의미 있게 보고 다음 제출부터는 틀린 문제인데 복기한다는 느낌으로 첫 제출을 신중히 해야겠다!