## SW 역량테스트 - [백준] 감시 문제 풀이/해답/코드 (C++ / JAVA) 본문

Data Structures, Algorithm/SW 역량테스트

### SW 역량테스트 - [백준] 감시 문제 풀이/해답/코드 (C++ / JAVA)

hashnut 2020. 10. 15. 23:42

## SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다!

### 해답 코드 :

``````#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>

using namespace std;

typedef struct cctv {

int row;
int col;
int num;
int dir;

} cctv;

int N, M;
int map[8][8];
// Up, Right, Down, Left
int dR[4] = {-1, 0, 1, 0};
int dC[4] = {0, 1, 0, -1};
vector<cctv> cctvs;
vector<cctv> cctv_5;
int ans;

bool isRange(int x, int y) {
if (x < 0 || x >= N || y < 0 || y >= M) {
return false;
}
else return true;
}

void copy_map(int dst[8][8], int src[8][8]) {

for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
dst[i][j] = src[i][j];
}
}

}

// count zero in the map
void cnt_zero() {
int zeros = 0;

for (int i = 0; i < N;i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 0) zeros++;
}
}

ans = min(ans, zeros);
}

// change map : 0 to -1 ( '#' ), according to the direction
void paint_line(int r, int c, int dir) {

int t_r, t_c, i = dir;

t_r = r + dR[i];
t_c = c + dC[i];

while (isRange(t_r, t_c)) {

if (map[t_r][t_c] == 0) {
map[t_r][t_c] = -1;
}
else if (map[t_r][t_c] == 6) {
break;
}
// else : -1, 1, 2, 3, 4, 5
// just update;

t_r += dR[i];
t_c += dC[i];

}
}

void paint() {

cctv tv;

for (int i = 0; i < cctvs.size(); i++) {
tv = cctvs[i];

if (tv.num == 1) {
paint_line(tv.row, tv.col, tv.dir);
}
else if (tv.num == 2) {
paint_line(tv.row, tv.col, tv.dir);
paint_line(tv.row, tv.col, (tv.dir + 2) % 4);
}
else if (tv.num == 3) {
paint_line(tv.row, tv.col, tv.dir);
paint_line(tv.row, tv.col, (tv.dir + 1) % 4);
}
else if (tv.num == 4) {
paint_line(tv.row, tv.col, tv.dir);
paint_line(tv.row, tv.col, (tv.dir + 1) % 4);
paint_line(tv.row, tv.col, (tv.dir + 2) % 4);
}

}

}

// Allocate direction to each CCTV, with DFS
// 1 : one direction
// 2 : two (180') direction
// 3 : two (90') direction
// 4 : three direction
// 5 : four direction
void monitor(int next) {

if (next == cctvs.size()) {
paint();
cnt_zero();
return;
}

int temp[8][8];

copy_map(temp, map);

for (int d = 0; d < 4; d++) {

cctvs[next].dir = d;
monitor(next+1);
// restore map
copy_map(map, temp);

}

}

int main() {

cin >> N >> M;

cctv t_cctv;
ans = INT32_MAX;

for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> map[i][j];
if (map[i][j] > 0 && map[i][j] < 5) {
t_cctv = {i, j, map[i][j], 0};
cctvs.push_back(t_cctv);
}
// Paint for CCTV 5, beforehand
else if (map[i][j] == 5) {
t_cctv = { i, j, map[i][j], 0 };
cctv_5.push_back(t_cctv);
}
}
}

// Paint for CCTV 5, beforehand
cctv tv;
for (int i = 0; i < cctv_5.size(); i++) {
tv = cctv_5[i];
paint_line(tv.row, tv.col, 0);
paint_line(tv.row, tv.col, 1);
paint_line(tv.row, tv.col, 2);
paint_line(tv.row, tv.col, 3);
}

monitor(0);

cout << ans << endl;

}``````

SW 역량테스트 준비 - [모의 SW 역량테스트] 풀이 / 코드 / 답안 (C++ / JAVA)

SW 역량테스트 준비 - C++ 코드, Java 코드

SW 역량테스트 준비 - 백준 알고리즘 문제

#### 'Data Structures, Algorithm > SW 역량테스트' 카테고리의 다른 글

 SW 역량테스트 - [백준] 큐빙 문제 풀이/해답/코드 (C++ / JAVA)  (0) 2020.10.15 2020.10.15 2020.10.15 2020.10.15 2020.10.15 2020.10.15