[백준 17142] 연구소3 (자바)

백준 17142번 연구소 3 (자바)

 

 

 

출처

www.acmicpc.net/problem/17142

17142번: 연구소 3

 

 

 

문제

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

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

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

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

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

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

 

 

 

입력

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

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

 

 

 

출력

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

 

 

 

입출력 예

 

 

 

접근 방법

이것도 삼성 기출... 기존 연구소1,2는 쉽게 풀었는데 이 문제는 조건 하나 추가되었다고 한참 헤맸다.

 

헷갈리는 조건은 '활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.' 이 조건인데

확산 중에 마주치면 0초부터 시작하는 건지.. 기존에 비어있던 칸처럼 시작하는 건지... 너무 헷갈렸다.

이 부분에 대한 힌트를 얻기 위해 찾아보았는데 그냥 신경 쓰지 말고 확산시키면 된다는 답변을 보았다.

 

기존 연구소 문제와 다르게 배열값을 입력받을 때 0의 개수를 카운트한 후, 확산 시에도 0의 개수를 카운트의 둘의 값을 비교하여 같으면 확산이 완료된 것이고 아니면 확산이 실패한 것으로 로직을 구성했습니다.

 

1. 0의 개수를 세고 확산 가능한 바이러스 리스트를 만들어 바이러스를 담는다.

 

2. 백트래킹으로 활성화 바이러스 조합을 만든다.

 

3. bfs로 바이러스를 확산시킨다.

    - 확산시 사용할 visit배열, 활성화 바이러스를 담을 큐를 만들어 바이러스를 담는다.

    - 최소 확산시간을 구해야 하므로 시간을 계산할 변수(value)와 0의 개수를 셀 변수(zeroCnt)를 생성한다.

    - 확산 후 기존에 계산했던 0의 개수와 확산 시 계산했던 0의 개수가 맞는지 비교한다.

    - 개수가 동일하면 value값을 반환하고, 다르면 확산에 실패한 것이므로 max값을 반환한다.

 

4. 최종값이 max값이면 -1을 반환하고, 아니면 최소 시간을 반환한다.

 

 

 

내 코드

 

 

 

고려할 점

1.0의 개수를 사용할 것

2. 백트래킹을 사용할 것

3. bfs를 사용할 것