백준 15683 감시 C풀이 - DFS

CCTV 의 위치와 종류가 주어져있고, 방의 구조가 주어진다.

CCTV로 감시할 수 있는 영역을 최대한으로 늘리는 것이 목표다.

 

문제의 조건은 다음과 같다.

1. 감시할 수 있는 부분을 최대한 늘릴 것

2. CCTV는 종류별로 감시할 수 있는 영역이 다르고, 방향 또한 바뀔 수 있다. 가령 1번은 오른쪽을 가리키고 있지만 돌려서 설치하면 위쪽을 감시하게 만들 수 있다.

 

문제의 접근 방식은 다음과 같다.

1. 완전탐색

 

문제의 해결방식은 다음과 같다.

1. CCTV를 돌려서 보는 방향을 바꿀 수 있다면 돌리면서 감시할 수 있는 영역을 확인한다.

2. 다른 CCTV에 대해서 1번을 수행한다.

 

방의 크기가 최대 8x8 이고 CCTV가 최대 8이므로 최악의 경우에도 6천가지 정도의 경우의 수를 탐색하면 된다.

 

고생했던 점은 다음과 같다.

1. CCTV의 방향을 정하고 감시할 수 있는 영역을 맵에 표시하기 -> 방향을 돌렸을 경우 감시할 방향을 어떻게 처리하는가에 대해서 많이 고민했다. 볼 수 있는 방향은 비트를 이용해서 표시했다.

오른쪽 방향을 기준(0번 비트)으로 왼쪽 90도씩 표현했다. 가령3번이면 0b0011 이므로 0x3 이 되고 2번이면 0b0101 이므로 0x5 가 된다.

감시 방향은 turnir 로 0이면 오른쪽 1이면 위쪽을 표현했으며, 감시 방향은 비트를 오른쪽으로 밀면서 확인했다.

 

전체 코드

#include <stdio.h>
#include <string.h>

int N, M;
int Map[9][9];
int c_Num;
int Min = 987654321;
typedef struct st {
	int y, x, type;
}CCTV;
CCTV cctv[9];
int used[9];


//오른방향 보는방향부터 왼쪽 90도씩상하좌우
int dir[] = { 0, 0x1, 0x5, 0x3, 0x7, 0xf };
int dy[] = { 0,-1,0,1 };
int dx[] = { 1,0,-1,0 };
int check() {
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (Map[i][j] == 0)cnt++;
		}
	}
	return cnt;
}
//감시되는 영역 채우기
void Fill(int idx, int turndir) {
//cctv 종류
	int cctvnum = Map[cctv[idx].y][cctv[idx].x];
	int i = 0;
	int y = cctv[idx].y;
	int x = cctv[idx].x;
    //한 번에 감시할 수 있는 방향별로 1 표시
	while (i < 4) {
		//방향 볼 수 있으면 채우기 turndir = 1이면 (위쪽) 1번 비트가 1이어야 위쪽 감시 가능
		if (dir[cctvnum] >> (turndir) & 0x1) {
			int ny = y + dy[i];
			int nx = x + dx[i];
            //감시할 수 있는 영역 모두 채우기
			for (;;) {
				if (ny < 0 || ny >= N || nx < 0 || nx >= M) break;
                //벽일 경우
				if (Map[ny][nx] == 6) break;
                //일반 방
				if (Map[ny][nx] == 0) {
					Map[ny][nx] = 1;//감시되는구역
				}
				ny += dy[i];
				nx += dx[i];

			}
		}
		turndir--;
		if (turndir < 0) turndir += 4;
		i++;
	}
	
}

void select(int num) {
//CCTV를 모두 설치함
	if (num == c_Num) {
		int tmp = check();
		if (tmp < Min) {
			Min = tmp;
		}
		return ;
	}
    //4방향으로 돌려본다.
	int turndir = 4;
    //현 맵 상태 저장용
	int tmpMap[9][9];
	memcpy(tmpMap, Map, sizeof(Map));
	//2번 5번은 2번 1번만 돌려도됨
	if (Map[cctv[num].y][cctv[num].x] == 2) turndir = 2;
	else if (Map[cctv[num].y][cctv[num].x] == 5) turndir = 1;
	for (int i = 0; i < turndir; i++) {
		//감시구역 표시
		Fill(num, i);
		
		//cctv설치
		select(num + 1);
		//감시구역 해제
		memcpy(Map, tmpMap, sizeof(Map));
	}
	return;


}

int solve() {
	Min = 987654321;
	select(0);
	return Min;
}

int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &Map[i][j]);
            // CCTV 입력
			if (Map[i][j] > 0 && Map[i][j] < 6) {
				cctv[c_Num].y = i;
				cctv[c_Num].x = j;
				cctv[c_Num++].type = Map[i][j];
			}
		}
	}
	int ans = solve();
	printf("%d\n", ans);
	return 0;
}