문제 : https://www.acmicpc.net/problem/15683
서론
완전탐색 + 시뮬레이션 문제.
혼자 풀어내지 못했다.
CCTV가 감시할 수 있는 모든 경우의 수를 재귀로 구현하려 했는데 재귀에서 리턴할때 해당 CCTV가 감시한 영역을 지워야한다. 이게 해결이 안되서 다른분의 코드를 봤다. 그리하여 탐색할때마다 현재 지도를 복사해서 리턴할때 복사한 지도를 불러오는 방법을 얻었다.
풀이
CCTV가 감시할 수 있는 모든 경우의 수를 얻어야한다.
그래서 재귀가 한단계씩 깊어질때마다 각 CCTV가 가질 수 있는 경우의 수를 재귀함수로 만들어준다.
void dfs(idx){
if(idx == cctv개수) 0의 개수 계산 후 리턴
if(cctv == 1){
dfs(idx+1, 위쪽)
dfs(idx+1, 오른쪽)
dfs(idx+1, 왼쪽)
dfs(idx+1, 아래쪽)
}
else if(cctv == 2){
dfs(idx+1, 위쪽과 아래쪽)
dfs(idx+1, 오른쪽과 왼쪽)
}
......
}
그리고 dfs로 방문할때마다 cctv가 각 방향으로 영역을 탐지하도록 draw함수를 만들고 수정한다.
void dfs(idx){
if(idx == cctv개수) 0의 개수 계산 후 리턴
y = cctv[idx].y
x = cctv[idx].x
if(cctv == 1){
draw(y, x, 위쪽)
dfs(idx+1)
draw(y, x, 오른쪽)
dfs(idx+1)
draw(y, x, 왼쪽)
dfs(idx+1)
draw(y, x, 아래쪽)
dfs(idx+1)
}
else if(cctv == 2){
draw(y, x, 위쪽)
draw(y, x, 아래쪽)
dfs(idx+1)
draw(y, x, 오른쪽)
draw(y, x, 왼쪽)
dfs(idx+1)
}
......
}
draw는 현재 cctv 위치에서 각 방향으로 탐지하는 함수다.
현재 위치에서 각 방향으로 지도가 끝날때까지 반복문으로 한칸씩 이동하며 탐지처리한다.
void draw(y, x, dir){
if(dir == 오른쪽){
for(int i=x;i<m;i++){
if(map[y][i] == 6) break
else map[y][i] = 1
}
}
else if(dir == 위쪽) {
....
}
그런데 위와 같이 하면 재귀가 리턴할때 탐지처리한 부분을 지우지 않고 그대로 리턴한다. 이를 방문하기 전에 현 지도를 백업지도에 복사하고 리턴하면 백업지도를 불러오는 방법으로 해결한다.
void dfs(idx){
if(idx == cctv개수) 0의 개수 계산 후 리턴
y = cctv[idx].y
x = cctv[idx].x
int mapCopy[8][8];
mapCopy = map;
if(cctv == 1){
draw(y, x, 위쪽)
dfs(idx+1)
map = mapCopy;
draw(y, x, 오른쪽)
dfs(idx+1)
map = mapCopy;
draw(y, x, 왼쪽)
dfs(idx+1)
map = mapCopy;
draw(y, x, 아래쪽)
dfs(idx+1)
map = mapCopy;
}
else if(cctv == 2){
draw(y, x, 위쪽)
draw(y, x, 아래쪽)
dfs(idx+1)
map = mapCopy;
draw(y, x, 오른쪽)
draw(y, x, 왼쪽)
dfs(idx+1)
map = mapCopy;
}
......
}
구현
// c++
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int map[8][8];
int n, m;
int result = 0x7f7f7f7f;
int camNum;
typedef struct st {
int y;
int x;
int cam;
}st;
vector<st>v;
void draw(int y, int x, int dir) { // dir : 상, 우, 하, 좌
if (dir == 0) {
for (int i = y; i >= 0; i--) {
if (map[i][x] == 6) break;
else map[i][x] = 1;
}
}
else if (dir == 1) {
for (int i = x; i < m; i++) {
if (map[y][i] == 6) break;
else map[y][i] = 1;
}
}
else if (dir == 2) {
for (int i = y; i < n; i++) {
if (map[i][x] == 6) break;
else map[i][x] = 1;
}
}
else if (dir == 3) {
for (int i = x; i >= 0; i--) {
if (map[y][i] == 6) break;
else map[y][i] = 1;
}
}
return;
}
void dfs(int idx) {
if (idx == camNum) {
int tmp = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map[i][j] == 0) tmp++;
}
}
result = min(result, tmp);
return;
}
int mapCopy[8][8];
memcpy(mapCopy, map, sizeof(mapCopy));
int cam = v[idx].cam;
int y = v[idx].y;
int x = v[idx].x;
if (cam == 1) {
for (int i = 0; i < 4; i++) {
draw(y, x, i);
dfs(idx + 1);
memcpy(map, mapCopy, sizeof(mapCopy));
}
}
else if (cam == 2) {
for (int i = 0; i < 2; i++) {
draw(y, x, i);
draw(y, x, i + 2);
dfs(idx + 1);
memcpy(map, mapCopy, sizeof(mapCopy));
}
}
else if (cam == 3) {
for (int i = 0; i < 4; i++) {
draw(y, x, i);
draw(y, x, (i + 1) % 4);
dfs(idx + 1);
memcpy(map, mapCopy, sizeof(mapCopy));
}
}
else if (cam == 4) {
for (int i = 0; i < 4; i++) {
draw(y, x, i);
draw(y, x, (i + 1) % 4);
draw(y, x, (i + 2) % 4);
dfs(idx + 1);
memcpy(map, mapCopy, sizeof(mapCopy));
}
}
else if (cam == 5) {
draw(y, x, 0);
draw(y, x, 1);
draw(y, x, 2);
draw(y, x, 3);
dfs(idx + 1);
memcpy(map, mapCopy, sizeof(mapCopy));
}
return;
}
int main() {
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] < 6) {
v.push_back({ i, j, map[i][j] });
camNum++;
}
}
}
for (int i = 0; i < 4; i++) dfs(0);
cout << result;
}
최근댓글