Algorithm/구현(Brute force, Back tracking, etc.)
백준 15683 감시
쩡류
2021. 11. 17. 12:05
728x90
https://www.acmicpc.net/problem/15683
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감
www.acmicpc.net
- 역시나 브루트포스, 백트래킹 문제이다. 구현 난이도 자체는 어렵지 않다.
- 감시카메라의 좌표를 벡터에 담고, 해당 카메라가 가질 수 있는 모든 경우의 수에 대해 조사를 한다. 감시가 되는 구역을 선택할 때
(1) 해당 구역이 벽이면 감시구역 조사를 중단한다.
(2) 해당 구역이 0이면 감시구역(-1)임을 표시한다.
(3) 해당 구역이 감시카메라이거나 이미 감시된 구역인 경우 continue한다.
- 또한, 각 재귀 호출마다 이전 상태로 돌아갈 temp1을 두고, 전역으로 temp2를 두어서 temp2는 마지막 사각지대 조사에 사용되도록 한다.
- 문제를 꼼꼼히 읽자. 감시카메라가 있는 부분을 벽이 있는 부분과 동일한 로직으로 처리하는 바람에 시간이 오래 걸렸다..
- 코드를 리팩토링하면 훨씬 더 깔끔하게 구현할 수 있을 것이다. 하지만 나는 구현에 목적을 두어서 하드코딩을 했다.(귀찮은 것도 한몫)
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int n, m;
int answer = 100000000;
int map[8][8];
int temp2[8][8];
int num_of_camera;
void DFS(int cnt, vector<pair<int,int>>& v ) {
int temp1[8][8];
if (cnt == num_of_camera) {
int temp_answer = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (temp2[i][j] == 0) temp_answer++;
}
}
answer = min(answer, temp_answer);
return;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
temp1[i][j] = temp2[i][j];
}
}
int x = v[cnt].first;
int y = v[cnt].second;
int sort_of_camera = map[x][y];
if (sort_of_camera == 1) {
//상, 하, 좌, 우 4가지 case로 나누어 DFS진행
for (int i = x-1; i >= 0; i--) {
if (temp2[i][y] == 6) break;
else if (!temp2[i][y]) temp2[i][y] = -1;
else continue;
}
DFS(cnt+1, v);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
temp2[i][j] = temp1[i][j];
}
}
for (int i = x + 1; i < n; i++) {
if (temp2[i][y] == 6) break;
else if (!temp2[i][y]) temp2[i][y] = -1;
else continue;
}
DFS(cnt + 1, v);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
temp2[i][j] = temp1[i][j];
}
}
for (int i = y-1; i >= 0; i--) {
if (temp2[x][i] == 6) break;
else if (!temp2[x][i]) temp2[x][i] = -1;
else continue;
}
DFS(cnt + 1, v);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
temp2[i][j] = temp1[i][j];
}
}
for (int i = y+1; i < m; i++) {
if (temp2[x][i] == 6) break;
else if (!temp2[x][i]) temp2[x][i] = -1;
else continue;
}
DFS(cnt + 1, v);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
temp2[i][j] = temp1[i][j];
}
}
}
else if (sort_of_camera == 2) { // 상,하 / 좌,우
for (int i = x-1; i >= 0; i--) {
if (temp2[i][y] == 6) break;
else if (!temp2[i][y]) temp2[i][y] = -1;
else continue;
}
for (int i = x+1; i < n; i++) {
if (temp2[i][y] == 6) break;
else if (!temp2[i][y]) temp2[i][y] = -1;
else continue;
}
DFS(cnt + 1, v);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
temp2[i][j] = temp1[i][j];
}
}
for (int i = y-1; i >= 0; i--) {
if (temp2[x][i] == 6) break;
else if (!temp2[x][i]) temp2[x][i] = -1;
else continue;
}
for (int i = y+1; i < m; i++) {
if (temp2[x][i] == 6) break;
else if (!temp2[x][i]) temp2[x][i] = -1;
else continue;
}
DFS(cnt + 1, v);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
temp2[i][j] = temp1[i][j];
}
}
}
else if (sort_of_camera == 3) { // 3번 카메라 - 상/우, 우/하, 하/좌, 좌/상
for (int i = x-1; i >= 0; i--) {
if (temp2[i][y] == 6) break;
else if (!temp2[i][y]) temp2[i][y] = -1;
else continue;
}
for (int i = y+1; i < m; i++) {
if (temp2[x][i] == 6) break;
else if (!temp2[x][i]) temp2[x][i] = -1;
else continue;
}
DFS(cnt + 1, v);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
temp2[i][j] = temp1[i][j];
}
}
for (int i = y+1; i < m; i++) {
if (temp2[x][i] == 6) break;
else if (!temp2[x][i]) temp2[x][i] = -1;
else continue;
}
for (int i = x + 1; i < n; i++) {
if (temp2[i][y] == 6) break;
else if (!temp2[i][y]) temp2[i][y] = -1;
else continue;
}
DFS(cnt + 1, v);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
temp2[i][j] = temp1[i][j];
}
}
for (int i = x + 1; i < n; i++) {
if (temp2[i][y] == 6) break;
else if (!temp2[i][y]) temp2[i][y] = -1;
else continue;
}
for (int i = y - 1; i >= 0; i--) {
if (temp2[x][i] == 6) break;
else if (!temp2[x][i]) temp2[x][i] = -1;
else continue;
}
DFS(cnt + 1, v);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
temp2[i][j] = temp1[i][j];
}
}
for (int i = y - 1; i >= 0; i--) {
if (temp2[x][i] == 6) break;
else if (!temp2[x][i]) temp2[x][i] = -1;
else continue;
}
for (int i = x - 1; i >= 0; i--) {
if (temp2[i][y] == 6) break;
else if (!temp2[i][y]) temp2[i][y] = -1;
else continue;
}
DFS(cnt + 1, v);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
temp2[i][j] = temp1[i][j];
}
}
}
else if (sort_of_camera == 4) { // 좌/상/우, 상/우/하, 우/하/좌, 하/좌/상
for (int i = y - 1; i >= 0; i--) {
if (temp2[x][i] == 6) break;
else if (!temp2[x][i]) temp2[x][i] = -1;
else continue;
}
for (int i = x - 1; i >= 0; i--) {
if (temp2[i][y] == 6) break;
else if (!temp2[i][y]) temp2[i][y] = -1;
else continue;
}
for (int i = y + 1; i < m; i++) {
if (temp2[x][i] == 6) break;
else if (!temp2[x][i]) temp2[x][i] = -1;
else continue;
}
DFS(cnt + 1, v);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
temp2[i][j] = temp1[i][j];
}
}
for (int i = x - 1; i >= 0; i--) {
if (temp2[i][y] == 6) break;
else if (!temp2[i][y]) temp2[i][y] = -1;
else continue;
}
for (int i = y + 1; i < m; i++) {
if (temp2[x][i] == 6) break;
else if (!temp2[x][i]) temp2[x][i] = -1;
else continue;
}
for (int i = x + 1; i < n; i++) {
if (temp2[i][y] == 6) break;
else if (!temp2[i][y]) temp2[i][y] = -1;
else continue;
}
DFS(cnt + 1, v);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
temp2[i][j] = temp1[i][j];
}
}
for (int i = y + 1; i < m; i++) {
if (temp2[x][i] == 6) break;
else if (!temp2[x][i]) temp2[x][i] = -1;
else continue;
}
for (int i = x + 1; i < n; i++) {
if (temp2[i][y] == 6) break;
else if (!temp2[i][y]) temp2[i][y] = -1;
else continue;
}
for (int i = y - 1; i >= 0; i--) {
if (temp2[x][i] == 6) break;
else if (!temp2[x][i]) temp2[x][i] = -1;
else continue;
}
DFS(cnt + 1, v);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
temp2[i][j] = temp1[i][j];
}
}
for (int i = x + 1; i < n; i++) {
if (temp2[i][y] == 6) break;
else if (!temp2[i][y]) temp2[i][y] = -1;
else continue;
}
for (int i = y - 1; i >= 0; i--) {
if (temp2[x][i] == 6) break;
else if (!temp2[x][i]) temp2[x][i] = -1;
else continue;
}
for (int i = x - 1; i >= 0; i--) {
if (temp2[i][y] == 6) break;
else if (!temp2[i][y]) temp2[i][y] = -1;
else continue;
}
DFS(cnt + 1, v);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
temp2[i][j] = temp1[i][j];
}
}
}
else if (sort_of_camera == 5) { // 상/하/좌/우
for (int i = x - 1; i >= 0; i--) {
if (temp2[i][y] == 6) break;
else if (!temp2[i][y]) temp2[i][y] = -1;
else continue;
}
for (int i = x + 1; i < n; i++) {
if (temp2[i][y] == 6) break;
else if (!temp2[i][y]) temp2[i][y] = -1;
else continue;
}
for (int i = y - 1; i >= 0; i--) {
if (temp2[x][i] == 6) break;
else if (!temp2[x][i]) temp2[x][i] = -1;
else continue;
}
for (int i = y + 1; i < m; i++) {
if (temp2[x][i] == 6) break;
else if (!temp2[x][i]) temp2[x][i] = -1;
else continue;
}
DFS(cnt + 1, v);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
temp2[i][j] = temp1[i][j];
}
}
}
}
int main() {
cin >> n >> m;
vector<pair<int, int>> v;
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] != 6) {
v.push_back({ i,j });
}
temp2[i][j] = map[i][j];
}
}
num_of_camera = v.size();
DFS(0, v);
cout << answer << '\n';
return 0;
}