제출 코드
- 사용 알고리즘 :
조합,BFS
벽을 세울수 있는 모든 경우를 구하고, 그 때마다 각 바이러스 지점에서 어디까지 퍼지는지 탐색.
이번에도 조합 코드 짜는 부분에서 발목잡혀서 너무 오래걸렸다.
일단 이차원 배열 안에서 경우의 수를 구한적이 처음이라, 재귀로 넘어갈 때 다음 i와 j값을 넘겨주는 과정에서 여러번 실수해서, 무한루프에 빠지거나 전체 경우를 탐색하지 않아서 틀렸다.
또한, 값을 잘 구해두고 내가 벽을 추가한 것들까지 포함해서 안전구역을 세는 바람에 틀렸다.
익숙해질 만 해도 절대 안익숙해지고 매번 틀리는 게 조합문제다. 언제쯤 익숙해질려고 그럴까…
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
package gold;
import java.io.BufferedReader;
import java.io.IOException;
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 G14502_lab {
static int N, M, non_safe_min = Integer.MAX_VALUE, origin_safe=0;
static int[][] map;
static List<Node> virus = new ArrayList<>();
static int[] di = {-1, 0, 1, 0};
static int[] dj = {0, 1, 0, -1};
static class Node{
int i, j;
Node(int i, int j){
this.i = i;
this.j = j;
}
}
static void perm(int n, int start_i, int start_j) {
if(n==3) {
non_safe_min = Math.min(non_safe_min, checkVirus());
return;
}
for(int i=start_i; i<N; i++) {
for(int j=(i==start_i?start_j:0); j<M; j++) {
if(map[i][j] != 0) continue;
map[i][j] = -1;
if(j==M-1) perm(n+1, i+1, 0);
else perm(n+1, i, j+1);
map[i][j] = 0;
}
}
}
static int checkVirus() {
boolean[][] visit = new boolean[N][M];
int non_safe = 0;
for(Node start : virus) {
Queue<Node> queue = new LinkedList<>();
queue.add(start);
while(!queue.isEmpty()) {
Node now = queue.poll();
for(int d=0; d<4; d++) {
int ni = now.i + di[d];
int nj = now.j + dj[d];
if(ni<0 || ni>=N || nj<0 || nj>=M || visit[ni][nj] || map[ni][nj]!=0) continue;
visit[ni][nj] = true;
if(++non_safe == non_safe_min) return non_safe;
queue.add(new Node(ni, nj));
}
}
}
return non_safe;
}
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());
map = new int[N][M];
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if(map[i][j]==2) virus.add(new Node(i, j));
else if(map[i][j]==0) origin_safe++;
}
}
perm(0, 0, 0);
System.out.println(origin_safe - non_safe_min - 3);
}
}