문제/백준
백준 17121 연구소2 [JAVA]
javaju
2021. 9. 2. 00:40
17141번: 연구소 2
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이
www.acmicpc.net
풀이 방법
모든 빈칸에 바이러스를 퍼뜨리는 최소 시간을 구하는 문제였습니다.
저는 먼저 이렇게 크게
1. 바이러스가 놓일 수 있는 연구소 위치를 list에 담기
2. 조합을 이용해 전체 바이러스 개수 중 M개 선택하기
3. 선택한 바이러스 퍼뜨리기
4. 바이러스가 퍼지는 최소 시간 구하기
이 순서로 구현했습니다.
조합을 이용해 M개의 바이러스 놓을 칸을 정했다면 spread() 메서드에서 상 하 좌 우로 이동하면서
바이러스를 퍼지게했습니다. 모든 바이러스가 퍼진 뒤에는, 최소 시간을 구해야 하기 때문에 time() 메서드를 통해서
모든 빈 칸에 바이러스가 퍼졌는지 확인과 함께 퍼뜨리는 최소 시간을 구해주었습니다.
이렇게 모든 바이러스가 놓일 수 있는 경우를 확인한 후 가장 최소 시간을 마지막에 출력해주었습니다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main_BJ_17121_연구소2 {
static class info{
int x, y;
public info(int x, int y) {
super();
this.x = x;
this.y = y;
}
}
static int N,M, time = Integer.MAX_VALUE;
static int [][] map, copy;
static int [] dx = {-1,0,1,0};
static int [] dy = {0,1,0,-1};
static ArrayList<info> list = new ArrayList<>();
static ArrayList<info> select = new ArrayList<>();
static Queue<info> queue = new LinkedList<>();
static boolean [][] selected;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); //연구소 크기
M = Integer.parseInt(st.nextToken()); //바이러스 개수
map = new int[N][N];
selected = new boolean[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]==1) map[i][j]= -1;
else if(map[i][j]==2) {
list.add(new info(i,j));
map[i][j] =0;
}
}
}
comb(0,0);
if(time==Integer.MAX_VALUE) System.out.println(-1);
else System.out.println(time);
}
public static void comb(int cnt, int start) {
if(cnt==M) {
// 바이러스 퍼지기 & 최소 시간 확인
spread();
return;
}
for(int i=start;i<list.size();i++) {
int x = list.get(i).x;
int y = list.get(i).y;
if(selected[x][y]) continue;
select.add(new info(x,y));
selected[x][y] = true;
comb(cnt+1,i+1);
selected[x][y] = false;
select.remove(select.size()-1);
}
}
public static void spread() {
transfer();
copy();
while(!queue.isEmpty()) {
info temp = queue.poll();
for(int i=0;i<4;i++) {
int nx = temp.x+dx[i];
int ny = temp.y+dy[i];
if(range(nx,ny) && copy[nx][ny]==0 && !selected[nx][ny]) {
copy[nx][ny] = copy[temp.x][temp.y]+1;
queue.add(new info(nx,ny));
}
}
}
if(time()!=-1 && time>time()) time=time();
}
public static void copy() {
copy = new int[N][N];
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
copy[i][j]=map[i][j];
}
}
}
public static boolean range(int x, int y) {
return x>=0 && x<N && y>=0 && y<N;
}
public static void transfer() {
for(int i=0;i<select.size();i++) {
queue.add(new info(select.get(i).x, select.get(i).y));
}
}
public static int time() {
int min=0, count=0;
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
if(copy[i][j]>min) min = copy[i][j];
if(copy[i][j]==0) count++;
}
}
if(count!=M) return -1;
return min;
}
}
|
cs |