BOJ 17142
위 문제는 백준 사이트의 알고리즘 17142 문제에 관한 설명입니다.
문제
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고,
바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다.
가장 처음에 모든 바이러스는 비활성 상태이고,
활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 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을 출력한다.
package 삼성기출;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class BOJ17142연구소3 {
static int[][] map;
static boolean[][] visit;
static boolean[] check;
static int[] dx = { 0, 0, 1, -1 };
static int[] dy = { 1, -1, 0, 0 };
static int N, M, answer = Integer.MAX_VALUE;
static int emptyCount = 0;
static List<Virus> virusList = new ArrayList<Virus>();
static List<Virus> selectedList = new ArrayList<Virus>();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if (map[i][j] == 0) {
emptyCount++;
}
if (map[i][j] == 2) {
virusList.add(new Virus(i, j));
}
}
}
if (emptyCount == 0)
System.out.println(0);
else {
check = new boolean[virusList.size()];
combination(0);
System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
}
}
private static void combination(int index) {
if (selectedList.size() == M) {
spread();
return;
}
if (index == virusList.size()) {
return;
}
for (int i = index; i < virusList.size(); i++) {
if (!check[i]) {
check[i] = true;
selectedList.add(new Virus(virusList.get(i).x, virusList.get(i).y));
combination(i + 1);
selectedList.remove(selectedList.size() - 1);
check[i] = false;
}
}
}
private static void spread() {
visit = new boolean[N][N];
Queue<Virus> queue = new LinkedList<Virus>();
for (Virus temp : selectedList)
queue.offer(temp);
int count = 0;
int time = 1;
while (!queue.isEmpty()) {
int queueSize = queue.size();
while (queueSize-- > 0) {
Virus temp = queue.poll();
for (int i = 0; i < 4; i++) {
int nextX = temp.x + dx[i];
int nextY = temp.y + dy[i];
if (isIn(nextX, nextY) && !visit[nextX][nextY] && map[nextX][nextY] != 1) {
visit[nextX][nextY] = true;
if (map[nextX][nextY] == 0)
count++;
if (count == emptyCount) {
if (answer > time)
answer = time;
return;
}
queue.offer(new Virus(nextX, nextY));
}
}
}
time++;
}
}
private static boolean isIn(int nextX, int nextY) {
if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N)
return false;
else
return true;
}
static class Virus {
int x;
int y;
public Virus(int x, int y) {
this.x = x;
this.y = y;
}
}
}
이번 문제는 시뮬레이션 문제입니다.
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if (map[i][j] == 0) {
emptyCount++;
}
if (map[i][j] == 2) {
virusList.add(new Virus(i, j));
}
}
}
if (emptyCount == 0)
System.out.println(0);
else {
check = new boolean[virusList.size()];
combination(0);
System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
}
}
메인의 입력부 입니다.
N과 M을 받아서 NxN 만큼의 map을 만듭니다.
그리고 맵에다가 각 값을 받아서 넣어주는데 0인 값이 있다면
비어있는 갯수를 나타내는 0을 늘려줍니다.
2라면 바이러스의 위치이므로 바이러스를 활성으로 변하게 합니다.
0의 갯수가 없다면 확산할 필요가 없이 값은 0 입니다.
아니라면 check하는 배열을 바이러스의 크기만큼 만들어주고
조합을 이용해줍니다.
조합부분
private static void combination(int index) {
if (selectedList.size() == M) {
spread();
return;
}
if (index == virusList.size()) {
return;
}
for (int i = index; i < virusList.size(); i++) {
if (!check[i]) {
check[i] = true;
selectedList.add(new Virus(virusList.get(i).x, virusList.get(i).y));
combination(i + 1);
selectedList.remove(selectedList.size() - 1);
check[i] = false;
}
}
}
바이러스의 갯수들 중 M개만큼을 뽑아내야하기 때문에
현재 M개를 뽑았다면 확산을 해야하는지 조건문으로 검사합니다.
M개만큼 뽑았으면 확산을 시켜줍시다.
만약 index가 바이러스 갯수와 같다면 쓸모없으니 반환시켜줍니다.
반복문 부분은 뽑은적이 있는가 확인하고,
하나씩 뽑고, 안 뽑고를 반복해줍니다.
BFS 부분
private static void spread() {
visit = new boolean[N][N];
Queue<Virus> queue = new LinkedList<Virus>();
for (Virus temp : selectedList)
queue.offer(temp);
int count = 0;
int time = 1;
while (!queue.isEmpty()) {
int queueSize = queue.size();
while (queueSize-- > 0) {
Virus temp = queue.poll();
for (int i = 0; i < 4; i++) {
int nextX = temp.x + dx[i];
int nextY = temp.y + dy[i];
if (isIn(nextX, nextY) && !visit[nextX][nextY] && map[nextX][nextY] != 1) {
visit[nextX][nextY] = true;
if (map[nextX][nextY] == 0)
count++;
if (count == emptyCount) {
if (answer > time)
answer = time;
return;
}
queue.offer(new Virus(nextX, nextY));
}
}
}
time++;
}
}
확산부분입니다.
queue에다가 선택했던 임시로 다 옮겨 준 후 BFS를 실행합니다.
턴마다 queue의 사이즈만큼을 확인했고,
빈공간의 count가 기존의 emptyCount와 같다면 빈공간이 이젠 없으므로 반환시킵니다.