문제
입력
첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.
CCTV의 최대 개수는 8개를 넘지 않는다.
출력
첫째 줄에 사각 지대의 최소 크기를 출력한다.
예제
코드
|
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
137
138
139
140
141
142
143
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main_BJ_15683_감시 {
static class CCTV{
int x, y, type;
public CCTV(int x, int y, int type) {
this.x = x;
this.y = y;
this.type = type;
}
}
static int N,M, min = Integer.MAX_VALUE;
static int [][] map;
static ArrayList<CCTV> list = new ArrayList<>();
static int [] dx = {-1,0,1,0};
static int [] dy = {0,1,0,-1};
static int [][] type1 = {{0},{1},{2},{3}};
static int [][] type2 = {{0,2},{1,3}};
static int [][] type3 = {{0,1},{1,2},{2,3},{3,0}};
static int [][] type4 = {{0,1,2},{1,2,3},{2,3,0},{3,0,1}};
static int [][] type5 = {{0,1,2,3}};
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][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]!=0 && map[i][j]!=6) list.add(new CCTV(i,j, map[i][j]));
}
}
dfs(0,map);
System.out.println(min);
}
public static void dfs(int cnt, int[][] init) {
if(cnt == list.size()) {
int count=0;
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
if(init[i][j]==0) count++;
}
}
min = Math.min(min, count);
return;
}
CCTV cctv = list.get(cnt);
int [][] visited = new int[N][M];
if(cctv.type==1) {
for(int i=0;i<4;i++) {
copy(visited, init); // map배열 복사
see(cctv.x, cctv.y, visited, i, type1);
dfs(cnt+1, visited);
}
}
else if(cctv.type==2) {
for(int i=0;i<2;i++) {
copy(visited, init);
see(cctv.x, cctv.y, visited,i,type2);
dfs(cnt+1, visited);
}
}
else if(cctv.type==3) {
for(int i=0;i<4;i++) {
copy(visited, init);
see(cctv.x, cctv.y, visited,i, type3);
dfs(cnt+1, visited);
}
}
else if(cctv.type==4) {
for(int i=0;i<4;i++) {
copy(visited, init);
see(cctv.x, cctv.y, visited,i, type4);
dfs(cnt+1, visited);
}
}else {
copy(visited, init);
see(cctv.x, cctv.y, visited,0, type5);
dfs(cnt+1, visited);
}
}
public static void see(int x, int y, int[][] visited, int index, int[][] type) {
visited[x][y] = 1;
for(int i=0;i<type[index].length;i++) {
int nx =x+dx[type[index][i]];
int ny =y+dy[type[index][i]];
while(range(nx,ny) && map[nx][ny]!=6) {
visited[nx][ny] =1;
nx += dx[type[index][i]];
ny += dy[type[index][i]];
}
}
}
public static boolean range(int x, int y) {
return x>=0 && y>=0 && x<N && y<M;
}
public static void copy(int [][] target , int [][] init) {
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
target[i][j] = init[i][j];
}
}
}
}
|
cs |
'문제 > 백준' 카테고리의 다른 글
| 백준 7562번 나이트의 이동 [JAVA] (0) | 2021.06.11 |
|---|---|
| 백준 4485번 녹색 옷 입은 애가 젤다지? [JAVA] (0) | 2021.04.21 |
| 백준 13905번 세부 [JAVA] (0) | 2021.04.21 |
| 백준 2239번 스토쿠 [JAVA] (0) | 2021.04.21 |
| 백준 1238번 파티 [JAVA] (0) | 2021.04.21 |