반응형
📖 문제
17141번: 연구소 2
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러
www.acmicpc.net
💡 풀이 방식
• 조합(DFS) + BFS
필요 자료구조
- 인접한 4방향 칸 탐색용 dx/dy 배열
- BFS용 방문 표시용 2차원 boolean형 배열
- 바이러스 위치 저장용 리스트 virusList
- 뽑은 바이러스 M개 저장할 임시 리스트 tmpList
1. 연구소 정보를 저장하면서, 바이러스 위치도 저장한다.
2. 조합(DFS)으로 바이러스 위치들 중 M개를 뽑아 뽑은 칸에서 BFS 탐색을 통해 바이러스를 퍼뜨리는 시간을 계산한다.
[바이러스 위치들 중 M개를 뽑는 메소드 (조합) ]
chk = new boolean[virusList.size()];
dfs(0, 0);
private static void dfs(int idx, int cnt) {
if(cnt == M) {
bfs(); // 바이러스 퍼뜨리기
return;
}
for(int i = idx ; i < virusList.size() ; i++) {
if(!chk[i]) {
chk[i] = true;
tmpList.add(i);
dfs(i + 1, cnt + 1);
chk[i] = false;
tmpList.remove(tmpList.size() - 1);
}
}
}
[바이러스 퍼뜨리는 메소드 (BFS) ]
private static void bfs() {
Queue<int[]> q = new ArrayDeque<>();
visited = new boolean[N][N];
int result = 0;
// 바이러스들 방문 처리하고, 큐에 추가하기
for(int i : tmpList) {
int x = virusList.get(i)[0];
int y = virusList.get(i)[1];
visited[x][y] = true;
q.add(new int[]{x, y});
}
while(!q.isEmpty()) {
int size = q.size();
for(int i = 0 ; i < size ; i++) { // 다 뽑는 거 아니고, 큐 사이즈만큼만 (= M개만)
int[] now = q.poll();
// 바이러스의 인접한 4칸 탐색
for(int d = 0 ; d < 4 ; d++) {
int nx = now[0] + dx[d];
int ny = now[1] + dy[d];
if(!inRange(nx,ny) || visited[nx][ny]) continue;
if(lab[nx][ny] != 1) {
visited[nx][ny] = true;
q.add(new int[] {nx, ny});
}
}
}
result++; // 시간 +1
}
if(chk()) { // 모든 칸이 감염된 경우, 정답 갱신
answer = Math.min(answer, result - 1);
}
}
💥 유의사항
큐의 사이즈만큼만 갯수 뽑아서 bfs 진행하기!
🔺 코드
|
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
|
import java.util.*;
import java.io.*;
public class Main {
static final int INF = Integer.MAX_VALUE;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
static int N,M;
static int[][] lab;
static boolean[][] visited;
static List<int[]> virusList = new ArrayList<>(); // 바이러스 놓을 수 있는 칸
static List<Integer> tmpList = new ArrayList<>(); // 임시 리스트
static boolean[] chk;
static int answer = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken()); // 놓을 수 있는 바이러스 개수
// 1. 연구소 정보 저장하기
lab = new int[N][N];
for(int i = 0 ; i < N ; i++) {
String[] str = br.readLine().split(" ");
for(int j = 0 ; j < N ; j++) {
lab[i][j] = str[j].charAt(0) - '0';
// 바이러스 위치 저장하기
if(lab[i][j] == 2) {
virusList.add(new int[]{i, j});
}
}
}
// 2. M개의 바이러스 선택하기
chk = new boolean[virusList.size()];
dfs(0, 0);
System.out.println(answer == INF ? -1 : answer);
}
private static void dfs(int idx, int cnt) {
// 3. 선택한 바이러스에서 BFS로 바이러스 퍼뜨리는 최소 시간 구하기
if(cnt == M) {
bfs();
return;
}
for(int i = idx ; i < virusList.size() ; i++) {
if(!chk[i]) {
chk[i] = true;
tmpList.add(i);
dfs(i + 1, cnt + 1);
chk[i] = false;
tmpList.remove(tmpList.size() - 1);
}
}
}
private static void bfs() {
Queue<int[]> q = new ArrayDeque<>();
visited = new boolean[N][N];
int result = 0;
// 바이러스들 방문 처리하고, 큐에 추가하기
for(int i : tmpList) {
int x = virusList.get(i)[0];
int y = virusList.get(i)[1];
visited[x][y] = true;
q.add(new int[]{x, y});
}
while(!q.isEmpty()) {
int size = q.size();
for(int i = 0 ; i < size ; i++) {
int[] now = q.poll();
// 바이러스의 인접한 4칸 탐색
for(int d = 0 ; d < 4 ; d++) {
int nx = now[0] + dx[d];
int ny = now[1] + dy[d];
if(!inRange(nx,ny) || visited[nx][ny]) continue;
if(lab[nx][ny] != 1) {
visited[nx][ny] = true;
q.add(new int[] {nx, ny});
}
}
}
result++; // 시간 +1
}
if(chk()) { // 모든 칸이 감염된 경우, 정답 갱신
answer = Math.min(answer, result - 1);
}
}
// 모든 칸이 감염됐는지 판별하는 함수
private static boolean chk() {
for(int i = 0 ; i < N ; i++) {
for(int j = 0 ; j < N ; j++) {
if(lab[i][j] != 1 && !visited[i][j])
return false;
}
}
return true;
}
private static boolean inRange(int x, int y) {
return 0 <= x && x < N && 0 <= y && y < N;
}
}
|
cs |
➕ 다른 풀이 방식
- 완전탐색으로 모든 칸이 감염되었는지 확인하지 않고, 지날 수 있는 길의 수를 계산해서 감염 안된 칸이 있나 확인하심.
[백준 17141 : JAVA] 연구소 2 / BFS + 조합
문제 풀이 먼저 바이러스를 놓을 수 있는 k개의 위치 중 m개의 위치를 선정해야 한다. 이는 조합 ${}_k \mathrm{ C }_m$으로 나타낼 수 있다. 조합 알고리즘을 통해 m개의 시작 지점을 정한 후에는 BFS 탐
pangtrue.tistory.com
[백준] 17141 연구소 2.Java
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러
velog.io
- 개인적으론 이 풀이가 더 이해가 잘 되는 듯 ✅
[백준 17141] 연구소 2 -JAVA //le_effort//
연구소 2 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초512 MB197188860543.369%문제인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이
suhyeokeee.tistory.com
💦 어려웠던 점
- 벽이랑 바이러스 위치를 어떻게 처리할지 긴가민가 했다.
- 벽이냐/바이러스냐/빈 칸이냐 이걸 구분하는 데 고민을 좀 오래 했던 것 같다.
🧐 새로 알게 된 내용
- 큐 사이즈만큼만 갯수 뽑기
- 문제처럼 직접 칸을 채우면서 풀어보려고 했는데 그냥 횟수만 이렇게 구해도 되는 것이었다,,
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V | 240510 |
(+ 240510 2회독 : 36752KB, 332ms)
1시간 걸림!
97%에서 걸렸었고, 막혔던 예제는 이거였다.
모든 빈 칸에 바이러스 퍼뜨렸는지 확인할 때 처리를 빠뜨렸었다.
5 1
2 1 1 1 1
1 2 0 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
결과 : -1
코드 확인하기
|
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
|
import java.util.*;
import java.io.*;
public class Main {
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
static int N,M;
static int[][] lab;
static List<int[]> vList = new ArrayList<>(); // 바이러스 위치 저장 리스트
static boolean[] chk;
static int answer = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
lab = new int[N][N];
for(int i = 0 ; i < N ; i++) {
st = new StringTokenizer(br.readLine(), " ");
for(int j = 0 ; j < N ; j++) {
lab[i][j] = Integer.parseInt(st.nextToken());
if(lab[i][j] == 2) { // 바이러스 위치 저장
vList.add(new int[] {i,j});
}
}
}
chk = new boolean[vList.size()];
dfs(0, 0);
System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
}
private static void dfs(int idx, int cnt) {
if(cnt == M) { // 바이러스 심을 위치 M개 뽑기
bfs();
return;
}
for(int i = idx ; i < vList.size() ; i++) {
if(!chk[i]) {
chk[i] = true;
dfs(i + 1, cnt + 1);
chk[i] = false;
}
}
}
private static void bfs() {
boolean[][] visited = new boolean[N][N];
Queue<int[]> q = new ArrayDeque<>();
// 배열 복사하기
int[][] copy = new int[N][N];
for(int i = 0 ; i < N ; i++) {
for(int j = 0 ; j < N ; j++) {
copy[i][j] = lab[i][j];
}
}
// 뽑힌 바이러스들 > 큐에 추가하고, 방문 처리하고, 값 0으로 바꾸기
for(int i = 0 ; i < chk.length ; i++) {
if(chk[i]) {
int x = vList.get(i)[0];
int y = vList.get(i)[1];
q.add(new int[]{x,y});
visited[x][y] = true;
copy[x][y] = 0;
}
}
int time = 0;
while(!q.isEmpty()) {
int[] now = q.poll();
for(int d = 0 ; d < 4 ; d++) {
int nx = now[0] + dx[d];
int ny = now[1] + dy[d];
if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue; // 격자 범위 벗어나는 경우
if(copy[nx][ny] == 1 && lab[nx][ny] == 1) continue; // 벽인 경우
if(visited[nx][ny]) continue; // 방문한 적 있는 경우
visited[nx][ny] = true;
q.add(new int[] {nx, ny});
copy[nx][ny] = copy[now[0]][now[1]] + 1; // 바이러스 퍼뜨리는 시간 갱신
time = Math.max(time, copy[nx][ny]);
}
}
// 모든 빈 칸에 바이러스 퍼뜨렸는지 확인
for(int i = 0 ; i < N ; i++) {
for(int j = 0 ; j < N ; j++) {
if(copy[i][j] == 0 && lab[i][j] == 0)
return;
if(copy[i][j] == 2 && !visited[i][j])
return;
}
}
// 모든 빈 칸에 바이러스 있는 최소 시간 갱신
answer = Math.min(answer, time);
}
}
|
cs |
(참고)
[백준] code.plus(BFS 알고리즘,JAVA)17141번, 연구소 2
문제 링크 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원
tussle.tistory.com
반응형
'코테 > 백준' 카테고리의 다른 글
| [백준/JAVA] 10026번: 적록색약 (1) | 2024.04.25 |
|---|---|
| [백준/JAVA] 2225번: 합분해 (0) | 2024.04.25 |
| [백준/JAVA] 20058번: 마법사 상어와 파이어스톰 (0) | 2024.04.24 |
| [백준/JAVA] 15990번: 1, 2, 3 더하기 5 (0) | 2024.04.23 |
| [백준/JAVA] 8980번: 택배 (0) | 2024.04.22 |
