[백준 17142] 연구소 3 (C++)

A. 문제설명

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

17142번: 연구소 3

문제에 대한 자세한 설명은 링크 참조

 

1. N*N 배열크기 땅이 존재

2. 각 배열의 엔트리에는 빈칸, 벽, 바이러스가 존재

3. 여기서 주어진 바이러스 중, M개를 활성화 시키려고 한다. 즉, 전체 바이러스가 |V|개라면 M개가 활성화 바이러스, |V|-M개가 비활성화 바이러스가 됨

4. 이제 활성화된 바이러스들을 시작으로 주변에 퍼뜨리는데, 바이러스는 벽을 제외한 칸에 바이러스를 퍼뜨림

5. 여기서, 활성화 바이러스가 비활성화 바이러스를 만나면 비활성화 바이러스는 활성화 됨

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

 

B. 접근법

DFS(활성화 바이러스 조합 구하기) + BFS(바이러스 전파 시뮬레이션)

 

문제는 크게 두 개의 부분으로 나눌 수 있다. 1. DFS로 활성화 바이러스 조합 M개 고르기, 2. 고른 M개의 바이러스들을 전파시키는 시뮬레이션 BFS

 

여기서, 문제 자체만 놓고보면 그렇게 까다롭지 않지만, 우리는 조건 5의 활성화 바이러스가 비활성화 바이러스를 만나는 경우를 잘 고려하여야 한다. 아래 조건의 연구소 상태가 주어졌다고 가정하자.

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

그리고 바이러스 3개를 활성화시켜, 퍼뜨린 결과가 아래와 같다.

* 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 *

위의 연구소 상태에서 좌상단의 * 비활성화 바이러스 표시는, 어차피 도달시간이 6초이므로 상관없지만, 우하단의 * 비활성화 바이러스 표시는 도달시간이 5초이다. 좌상단을 무시하고 우하단의 비활성화 바이러스만 보았을 때 도달시간이 5초라고 생각할 수 있지만 그렇지 않다. 연구소 지도에 바이러스를 전부 퍼뜨리는 것이 목표이므로, 비활성화라도 우하단까지 퍼뜨리는 데 걸리는 시간은 4초라고 볼 수 있다.

 

그러면, 여기서 구현에서 주의해야할 것이, 비활성화 바이러스는 BFS 탐색에서 벽으로 감안해야할 수도 있겠지만, 그런 경우 조건 5의 활성화 바이러스가 비활성화 바이러스를 만나 활성화 바이러스가 되는 조건을 충족하지 못한다. 그렇다면 좀 더 섬세한 방법으로 비활성화 바이러스에 대한 처리방법을 생각해야 되는데, 그 것은 아래와 같다.

1. 비활성화 바이러스를 일반 엔트리로 생각하되, 마지막에 퍼진 위치가 비활성화 바이러스의 위치라면, 해당 위치를 시간 측정에서 제외할 것

2. 비활성화 바이러스가 활성화되어 퍼질 때는 일반 땅에서 퍼지는 것과 같이 기존 전파시간을 유지할 수 있을 것

위 두가지 조건을 잘 고려하여 구현해야 하는 것이다.

 

예시를 들어 설명하자면

예1. 비활성화 바이러스가 도달위치 맨 끝에 있는 경우

2 0 2
1 1 1
1 1 1

이 경우 아래와 같이 전파되며 전체 바이러스 전파시간은 1초가 된다.

0 1 *
- - -
- - -

 

예2. 비활성화 바이러스가 중간에 활성화되고 다시 바이러스를 전파하는 경우

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

이 경우는 중간에 비활성화 바이러스가 활성화로 변하며(#으로 표시) 전체 바이러스 전파 시간은 3초가 되어야 한다.

0 1 # 3
1 - - -
2 - - -
- - - -

 

내 코드에서 이에 대한 처리가 69번 라인에 되어 있다. arr가 처음에 받는 연구소 상태 배열이고, actArr가 바이러스를 전파시켜서 연구소 상태를 나타내는 배열인데, 

if(v.t != 0 && arr[v.x][v.y] == 2) actArr[v.x][v.y] = -4;

위와 같이 활성화 바이러스가 아닌 바이러스(0초 이후에 활성화된 바이러스)의 경우 따로 표시하여 마지막에 지도에 퍼진 시간을 계산할 때 비활성화->활성화로 변한 바이러스는 예외처리 되면서, 이 바이러스를 지나 다음 지역에는 다시 바이러스가 퍼질 수 있도록 처리하였다.

 

C. 풀이

1. DFS로 arr에 M수에 따라 바이러스 활성화 조합 선택

2. actArr에 활성바이러스 선택하여 0부터 바이러스 전파(BFS)

3. 활성이 비활성 만나면 -2->[시간]으로 변환해서 큐에 넣고 다시 전파시작

4. 벽을 제외한 모든 영역에 바이러스가 퍼질 때까지 반복

5. 비활성화 바이러스인 경우 -4로 따로 표시

6. 반복 중 최대의 시간을 출력(모두 퍼지지 못하는 경우 -1)

 

D. 내 코드