https://www.acmicpc.net/problem/15683
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할
www.acmicpc.net
CCTV구조체를 만들어서 CCTV의 좌표, 종류, 방향을 저장하게 했다.
방향은 나중에 모든 경우를 구해줄 때 저장한다.
모든 CCTV에 대해 방향을 정해줬으면 각 CCTV들의 감시 영역을 새로운 배열에 체크해주고
사각지대의 영역을 구해준다.
|
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
144
145
146
147
|
#include <iostream>
#include <vector>
using namespace std;
int n, m;
int ans;
int map[8][8];
int dx[] = { 0,-1,0,1 };
int dy[] = { -1,0,1,0 };
struct CCTV {
//감시카메라의 좌표
int x;
int y;
//감시카메라 종류 번호
int num;
//감시할 방향 (나중에 정해준다)
int dir;
CCTV(int x, int y, int num) : x(x), y(y), num(num){}
};
vector<CCTV> vt;
//감시영역을 체크
void start(int x, int y, int dir, int newmap[8][8]) {
while (true) {
//dir 방향으로 계속 감시 영역을 표시한다.
x += dx[dir];
y += dy[dir];
//범위 체크
if (x < 0 || y < 0 || x >= n || y >= m) break;
//벽이면 넘어갈 수 없다.
if (map[x][y] == 6) break;
//감시영역에 적당히 그냥 7넣어줬다.
newmap[x][y] = 7;
}
}
//모든 감시카메라들을 지정된 방향에 따라 감시영역을 표시한다.
int solve() {
int newmap[8][8];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
newmap[i][j] = map[i][j];
}
}
int vsize = vt.size();
int x, y, num,dir;
for (int i = 0; i < vsize; i++) {
x = vt[i].x;
y = vt[i].y;
num = vt[i].num;
dir = vt[i].dir;
//종류에 따라서 감시영역을 표시한다.
if (num == 1) {
//한방향 감시
start(x, y, dir, newmap);
}
else if (num == 2) {
//반대방향이 두방향 감시
start(x, y, dir, newmap);
start(x, y, (dir+2)%4, newmap);
}
else if (num == 3) {
//직각모양 두방향 감시
start(x, y, dir, newmap);
start(x, y, (dir+1)%4, newmap);
}
else if (num == 4) {
//세방향 감시
start(x, y, dir, newmap);
start(x, y, (dir + 1) % 4, newmap);
start(x, y, (dir + 2) % 4, newmap);
}
else if (num == 5) {
//네 방향 모두 감시
start(x, y, dir, newmap);
start(x, y, (dir + 1) % 4, newmap);
start(x, y, (dir + 2) % 4, newmap);
start(x, y, (dir + 3) % 4, newmap);
}
}
//처음에 사각지대였는데 감시영역을 표시한 이후에도 사각지대이면 cnt증가
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map[i][j] == 0 && newmap[i][j] == 0) cnt++;
}
}
//사각지대 수를 리턴
return cnt;
}
//모든 감시카메라에 대해서 방향을 정해준다.
void select(int index) {
if (index == vt.size()) {
int tmp = solve();
if (ans > tmp) ans = tmp;
return;
}
for (int i = 0; i <= 3; i++) {
vt[index].dir = i;
select(index + 1);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie();
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> map[i][j];
//감시카메라이면 벡터에 넣는다.
if (map[i][j] >= 1 && map[i][j] <= 5) {
vt.push_back(CCTV( i,j,map[i][j] ));
}
}
}
//정답이 될 수 있는 값보다 큰 값을 미리 저장
ans = 65;
select(0);
cout << ans << '\n';
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 11559. Puyo Puyo (0) | 2019.08.08 |
|---|---|
| [BOJ] 3190. 뱀 (0) | 2019.08.06 |
| [BOJ] 14500. 테트로미노 (0) | 2019.08.04 |
| [BOJ] 14499. 주사위 굴리기 (0) | 2019.08.04 |
| [BOJ] 14503. 로봇 청소기 (0) | 2019.08.04 |