[BOJ] 17142 연구소 3 (C/C++)

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을 출력한다.

---

아직 자소서를 시작도 안 했지만 이번에 삼성 인턴에 지원할 예정이다. 그래서 앞으로 계속 삼성 문제를 풀어보려고 한다.

 

삼성 기출을 풀면 거의 시뮬레이션, 구현, DFS, BFS가 많이 나오는 것 같다. 실제로 이 문제도 바이러스 시작점을 고르기 위해 조합이 필요했는데 이는 DFS로 구현했고, 바이러스가 퍼지는 과정은 BFS로 구현했다.

 

처음에 문제를 제대로 이해하지 못해서 좀 돌아왔다. 그리고 문제가 조금 모호하게 설명이 되어 있어서 주어진 예시를 이해하는 것도 시간이 좀 걸렸다. 결국 포인트는 어떤 좌표에 활성 바이러스가 없더라도 비활성 바이러스가 있다면 굳이 거기까지 전파시키지 않아도 된다는 것이었다. 그래서 BFS에 정보를 추가해줬다.

 

그리고 제한시간이 무려 0.25초라서 최적화 기법도 필요해보였다. 나는 전파시킬 필요가 있는 빈칸의 개수를 세어둬서 빈칸이 감염될 때마다 그 수를 저장했다. 그리고 모든 빈칸이 전파됐다면 비활성 바이러스밖에 남지 않았으므로 그냥 BFS를 종료하는 것으로 처리했다.

 

코드를 덕지덕지 쓰다보니 중간에 if 문이 많이 들어가서 가독성이 상당히 떨어졌다. 코드를 읽어도 흐름을 알기 상당히 어렵달까? 처음에 설계가 제대로 됐다면 이럴 일이 없었을 텐데....

 

 

후기)

문제를 두 번 풀어서 오래 걸렸지만 그리 어렵지는 않았다. 구현을 하면서도 실수를 많이 하지 않아서 디버깅도 거의 하지 않았다.