티스토리 뷰
문제 링크
https://www.acmicpc.net/problem/17141
17141번: 연구소 2
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러스는 퍼지게 된다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 빈 칸은 바이러스를 놓을 수 있는 칸이다. 바이러스는 상하좌우로
www.acmicpc.net
https://www.acmicpc.net/problem/17142
17142번: 연구소 3
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는
www.acmicpc.net
바이러스를 놓을 수 있는 자리가 정해져 있고, 그중 M개의 자리를 골라 최대한 빠르게 바이러스를 퍼뜨릴 수 있는 시간을 구해야 합니다.
연구소 2와 연구소 3은 시간제한을 빼면 사실상 같은 문제이므로 함께 포스팅합니다.
이걸 어떻게 푸나 싶지만 입력에서 2(바이러스를 놓을 수 있는 칸)의 개수가 10 이하입니다. 따라서 바이러스를 놓을 자리를 완전 탐색으로 구할 수 있습니다.
풀이
1) 바이러스를 놓을 수 있는 모든 칸에서 각각 bfs를 돌려 연구소의 각 칸에 바이러스가 퍼지는 시간을 저장해둡니다.
2-1) 완전 탐색으로 바이러스 M개를 배치할 칸들을 결정합니다.
2-2) 바이러스를 배치할 칸이 결정되면 연구소의 모든 칸에 대해, 각 칸마다 바이러스가 퍼지는 최소의 시간을 구하고, 각 칸에서 구한 최소 시간 중 최댓값을 구합니다. 이는 1)에서 저장한 시간으로 쉽게 구할 수 있습니다.
3) 바이러스를 배치하는 모든 경우의 수에 대해, 2-2)에서 구한 최댓값 중 최솟값이 정답이 됩니다.
최솟값 최댓값이 반복해서 나와 말장난 같지만 잘 생각해보면 간단한 풀이입니다. 구현 실력이 받쳐주지 않으면 코딩이 어려우실 수도 있습니다. 제 코드상으로 시간 복잡도는 $O(_{10}C_{M} * N^2M)$쯤 되겠네요.
예외처리로는 바이러스가 퍼질 수 없는 칸이 있을 경우를 생각해주셔야 합니다. 이때는 -1을 출력합니다.
또 연구소 2는 하던대로 짜시면 되는데, 연구소 3에서는 연구소에 빈칸(0)이 없는 경우 0을 출력해야 합니다.
정답 코드
연구소 2
연구소 3
'알고리즘 > 문제 풀이' 카테고리의 다른 글
| [BOJ] 백준 3649 로봇 프로젝트 (0) | 2019.10.15 |
|---|---|
| [BOJ] 백준 15971 두 로봇 (0) | 2019.10.15 |
| [2019 숭고한 캠프] 백준 17392 우울한 방학 (1) | 2019.08.18 |
| [2019 SCCC] 백준 17131 여우가 정보섬에 올라온 이유 (0) | 2019.06.04 |
| [2019 SCCC] 백준 17127 벚꽃이 정보섬에 피어난 이유 (2) | 2019.05.24 |