백준 17142번 연구소 3 :: 마이구미

이 글은 백준 알고리즘 문제 17142번 "연구소 3" 를 풀이한다.
삼성 SW 역량 테스트 문제이다.
문제 해결을 위해 DFS, BFS 2가지 모두 요구한다.
문제 링크 - https://www.acmicpc.net/problem/17142
DFS, BFS - https://mygumi.tistory.com/102

 

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

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

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

 

---

 

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

 

입력

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

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

---

 

문제에서 주어지는 것은 다음과 같다.

 

• 벽(1), 빈칸(0), 바이러스(2)가 존재한다.
• 바이러스는 비활성화, 활성화로 나뉜다.

 

바이러스는 비활성화, 활성화로 구분된다는 것을 정확히 이해해야한다.

활성화 바이러스가 비활성화 바이러스 칸으로 이동하면 비활성화 => 활성화로 변하게 된다.

이 부분을 고려하지 않으면, 채점이 거의 100% 에 다다를 때, "틀렸습니다" 를 볼 것이다.

이건 테스트 케이스를 통해 쉽게 이해할 수 있다.

 

INPUT
4 2
0 1 1 0
2 1 1 2
2 1 1 2
0 1 1 0

OUTPUT
2

 

INPUT

5 1
2 2 2 1 1
2 1 1 1 1
2 1 1 1 1
2 1 1 1 1
2 2 2 2 0

OUTPUT
1

 

문제에서 요구하는 것은 다음과 같다.

 

1. 바이러스는 입력에서 2로 주어지고, 주어진 바이러스 중에서 M개를 고른다.
2. 초마다 바이러스에 인접한 빈칸은 바이러스 퍼지게 된다.
3. 모든 빈칸에 바이러스가 퍼지는 시간을 구한다.

 

위 과정을 반복하면서 최소 시간을 찾는다.

일반적으로 DFS, BFS 문제에 익숙하다면, 1번 과정을 위해서 DFS, 2번 과정을 위해서 BFS 를 떠올릴 수 있다.

1번 과정을 위해 최대 10개 중 M개를 고르는 경우들에 대해 2번 과정을 동작해야한다.

* 1번 과정은 조합 공식으로는 10Cm 으로 나타낼 수 있다.

 

1번은 백트래킹을 통해 쉽게 구현할 수 있다.

익숙하지 않다면, https://mygumi.tistory.com/191 읽어보길 바란다.

 

1번 과정의 핵심 코드는 다음과 같다.

 

void find_case_dfs(int v, int cnt, int limit) {
    if (cnt == limit) {
        int result = spread_bfs();
        if (result >= 0 && min > result) {
            min = result;
        }
    } else {
        find_case_dfs(i, cnt + 1, limit);
    }
}

 

바이러스가 위치할 수 있는 M개의 경우에 대해서는 2번 과정을 동작한다.

그렇지 않으면, M개의 경우를 찾기 위해 1번 과정을 다시 재귀적으로 호출한다.

 

2번 과정은 BFS 를 사용해서 단순히 인접한 네 방향으로 확산시켜주면 된다.

 

while(!q.isEmpty()) {
    int point = q.poll();
    int y = point / N;
    int x = point % N;
    visited[y][x] = true;
    for (int k = 0; k < 4; k++) {
        int nextX = x + dx[k];
        int nextY = y + dy[k];
        if (0 <= nextX && nextX < N && 0 <= nextY && nextY < N) {
            if (!visited[nextY][nextX]) {
                visited[nextY][nextX] = true;
                if (copyMap[nextY][nextX] == 0 || copyMap[nextY][nextX] == 2) {
                    // ...............
                }
            }
        }
    }
}

 

주의할 점은 빈칸만을 고려해야하는 것이 아니라 비활성화 바이러스도 구분해주어야한다는 것이 핵심이다.

 

본인은 이 부분을 위해 두 가지 모두 큐에 넣으면서, 빈칸의 여부를 가지고 해결했다.

빈칸이 없는 채로 2번 과정이 이루어진다면, 초를 증가시키지 않고, 임시 변수에 따로 증가시킨다.

그리고 빈칸이 나온다면, 임시 초를 현재 초와 합쳐준다.

하지만 나오지 않는다면, 임시 초는 사용하지 않고 현재 초를 유지한다.

 

전체 코드와 위에서 언급한 테스트 케이스를 함께 보면, 조금 더 이해하기 수월할 것이다.

문제는 DFS, BFS 기본 지식만 가지고 있어도 충분히 풀 수 있다.

하지만 정답률이 높지 않은 것은 바이러스의 활성화, 비활성화 구분에 대한 함정이다.

 

Github - https://github.com/hotehrud/acmicpc/blob/master/SAMSUMG/17142.java

 

참고로 코드에서 N x N 연구소에 대한 접근은 행과 열로 접근하는 것이 아닌, 한가지 수로 접근하는 방식을 사용했다.

ex) N = 4 일 경우, (0, 4) => 4, (1,1) => 1 X 4 + 1 = 5

 

 

위와 같이 차례대로 접근하기 때문에 M개를 고르는 경우를 쉽게 파악할 수 있다.