- 생각
기존에 비슷한 문제를 푼 적이 있었다. 풀었던 코드에서 문제조건에 따라서 살짝 수정해주었다.
[JAVA] 백준 17141번 : 연구소 2
코드 정답 코드 : dfs를 통해 depth가 M일 때 bfs를 통해서 최소시간을 구해주었다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedLi..
qazyj.tistory.com
문제를 읽어보면 한가지 다른점은 비활성 상태인 바이러스 위치까지 전파할 필요가 없다는 것이다.
연구소2에서는 copy 함수에서 선택되지 않은 바이러스는 0으로 표시했다면, 연구소3에서는 -1로 표시했다.
이유는 바이러스가 전파될 때 비활성 상태인 바이러스를 통과해서 지나갈 수 있기 때문이다.
- 코드
정답 코드 : dfs를 통해 depth가 M일 때 bfs를 통해서 최소시간을 구해주었다.
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 {
private static int N, M, count, min;
private static int[][] array;
private static boolean[] check;
private static ArrayList<int[]> virus;
private static int[] x = { 0, 0, -1, 1 };
private static int[] y = { -1, 1, 0, 0 };
public static void main(String[] args) throws Exception {
SetData();
System.out.println(min);
}
private static void SetData() 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());
array = new int[N][N];
virus = new ArrayList<>();
count = 0;
min = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
array[i][j] = Integer.parseInt(st.nextToken());
if (array[i][j] == 2)
virus.add(new int[] { i, j });
if (array[i][j] == 0)
count++;
}
}
check = new boolean[virus.size()];
if (count != 0)
dfs(0, 0);
else
min = 0;
if(min == Integer.MAX_VALUE)
min = -1;
}
private static void dfs(int start, int depth) {
// Basecase
if (depth == M) {
int[][] tempArray = copyArray();
bfs(tempArray, count);
return;
}
for (int i = start; i < virus.size(); i++) {
check[i] = true;
dfs(i+1, depth + 1);
check[i] = false;
}
}
private static void bfs(int[][] tempArray, int count) {
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < virus.size(); i++) {
if (check[i])
queue.add(virus.get(i));
}
int time = 0;
while (!queue.isEmpty()) {
if (time >= min) break;
int length = queue.size();
for (int j = 0; j < length; j++) {
int[] location = queue.poll();
for (int direction = 0; direction < 4; direction++) {
int r = location[0] + x[direction];
int c = location[1] + y[direction];
if (r < 0 || c < 0 || r >= N || c >= N) continue;
if (tempArray[r][c] == 1 || tempArray[r][c] == 2) continue;
if (tempArray[r][c] == 0) count--;
tempArray[r][c] = 2;
queue.add(new int[] { r, c });
}
}
time++;
if (count == 0) {
min = time;
return;
}
}
}
private static int[][] copyArray() {
int[][] result = new int[N][N];
for (int i = 0; i < N; i++) {
System.arraycopy(array[i], 0, result[i], 0, N);
}
for (int i = 0; i < virus.size(); i++) {
if (!check[i]) {
int[] location = virus.get(i);
result[location[0]][location[1]] = -1;
}
}
return result;
}
}
'algorithm' 카테고리의 다른 글
| [BOJ/JAVA] 백준 11727번 : 2 x n 타일링 2 (0) | 2021.01.06 |
|---|---|
| [BOJ/JAVA] 백준 1463번 : 1로 만들기 (0) | 2021.01.05 |
| [BOJ/JAVA] 백준 1339번 : 단어 수학 (0) | 2021.01.04 |
| [BOJ/JAVA] 백준 2448번 : 별찍기 - 11 (0) | 2020.12.24 |
| [JAVA] 백준(BOJ) 1941번 : 소문난 칠공주 (0) | 2020.12.23 |
