[백준] 15683번: 감시

https://www.acmicpc.net/problem/15683

15683번: 감시

 

문제 이해

역시 모든 경우를 탐색해야 하는 문제이다.

CCTV의 최대 개수가 8개라고 하는 거부터가 그냥 DFS를 써라~ 하는 것 같다.

 

CCTV는 다섯개의 종류가 있고, 

1번, 3번, 4번의 경우 방향을 돌리면 4가지 경우의 수

2번의 경우 2가지 경우의 수

5번의 경우 1가지 경우의 수

가 있다.

 

i번 CCTV가 j방향을 가리킬 때 동서남북 중 k방향을 감시할 수 있는지를 dir라는 배열에 저장했다.

그리고 입력을 받을 때 CCTV의 위치와 종류를 C라는 배열에 저장해두었다.

 

DFS()

DFS를 통해서 각 CCTV의 방향을 결정한다.

예를 들어, CCTV가 3, 4, 5번으로 총 3개가 들어왔다면

3번 (4가지) * 4번(4가지) * 5번(1가지) = 16가지의 경우의 수를 따지면 된다. 

 

다시 말해, 3개의 depth를 가지는 DFS를 수행하면 된다.

sel이라는 배열에 3개의 CCTV의 방향을 저장해둔다.

만약 3개의 CCTV가 가리키는 방향을 다 정했다면, 이거에 맞춰서 맵에 표시를 해보면 된다.

표시는 Print_Sel()이라는 함수를 이용했다. 

void DFS(int cnt) {

	// 종료
	if (cnt >= ccnt) {
		// 다 골랐다.
		int res = Try_Watch();
		if (res < ans) ans = res;
		return;
	}

	// idx번을 고를 차례
	if (C[cnt].no == 2) { // 두 가지 경우의 수
		for (int i = 0; i < 2; i++) {
			sel[cnt] = i;
			DFS(cnt + 1);
		}
	}
	else if(C[cnt].no == 5){ // 한 가지
		sel[cnt] = 0;
		DFS(cnt + 1);
	}
	else {
		for (int i = 0; i < 4; i++) {
			sel[cnt] = i;
			DFS(cnt + 1);
		}
	}
}

 

Print_Sel()

원래 map을 손상시키지 않기 위해 tmpmap에 map을 복사해서 사용한다.

C[i].no 은 i번째 CCTV가 몇 번 CCTV인지 갖고 있다. 

sel[i] 에는 i번째 CCTV가 가리키는 방향이 있다.

그러므로 dir[C[i].no][sel[i]] 이라는 1차원 배열에는 i번째 CCTV가 감시할 수 있는 방향이 동서남북으로 저장되어있다. 

예를 들어, 1111 이라면 동서남북 다 감시할 수 있다는 뜻이다. 

 

그럼 이제, CCTV위치를 기준으로 1인 방향들을 탐색하며 -1로 바꿔준다.

이때 CCTV이면 통과할 수 있으므로 이 칸에 -1을 체크하진 않되, while문을 게속 돌린다.

벽이면 통과 불가능이므로 그냥 while문에서 break해버린다.

while(ny >= 0 && ny < N && nx >= 0 && nx < M){
  if (tmpmap[ny][nx] == 6) break; // 벽이면 막힘
  if (tmpmap[ny][nx] == 0){
    tmpmap[ny][nx] = -1;
	}
  ny += dy[j];
  nx += dx[j];
}

모든 CCTV에 대해 tmpmap 표시를 했으면 이제 사각지대가 몇 칸이 남았는지 확인한다.

그냥 이중 for문으로 tmpmap을 탐색한다.

 

최종 코드

#include <stdio.h>
#include <string.h>
#define MAXMN 8

int N, M;
int map[MAXMN + 5][MAXMN + 5];
int tmpmap[MAXMN + 5][MAXMN + 5];

int dy[] = { 0, 0, 1, -1 }; //동서남북
int dx[] = { 1, -1, 0, 0 };

typedef struct st1 {
	int y, x, no;
}CCTV;
CCTV C[8 + 2];
int ccnt;
int sel[8 + 2]; // 선택한 방향
int ans = 0x7fffffff;

// 방향
int dir[6][4][4] = {
	{{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}},
	{{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}, //1번 CCTV 동서남북 바라볼 때
	{{1, 1, 0, 0}, {0, 0, 1, 1}, {0, 0, 0, 0}, {0, 0, 0, 0}}, // 2번, CCTV 동 / 남 바라볼 때
	{{1, 0, 0, 1}, {1, 0, 1, 0}, {0, 1, 1, 0}, {0, 1, 0, 1}}, // 3번,
	{{1, 1, 0, 1}, {1, 0, 1, 1}, {1, 1, 1, 0}, {0, 1, 1, 1}}, // 4번,
	{{1, 1, 1, 1}, {0, 0, 0, 0}, {0, 0, 0, 0},  {0, 0, 0, 0}} // 5번, 하나밖에 없음 
};


void Get_Input(void) {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] != 6 && map[i][j] != 0) { // CCTV 저장
				C[ccnt].y = i, C[ccnt].x = j, C[ccnt++].no = map[i][j];
			}
		}
	}
}

void Print_Sel(void) {
	for (int i = 0; i < ccnt; i++) {
		printf("%d ", sel[i]);
	}
	printf("\n");
}

int Try_Watch(void) {
	//Print_Sel();
	// 이 disSel 상황에서 감시하는 곳 표시
	memset(tmpmap, 0, sizeof(tmpmap));
	memcpy(tmpmap, map, sizeof(map));
	for (int i = 0; i < ccnt; i++) {
		int d = sel[i];
		for (int j = 0; j < 4; j++) {
			if (dir[C[i].no][d][j] == 0) continue;
			int ny = C[i].y + dy[j];
			int nx = C[i].x+dx[j];
			while(ny >= 0 && ny < N && nx >= 0 && nx < M){
				if (tmpmap[ny][nx] == 6) break; // 벽이면 막힘
				if (tmpmap[ny][nx] == 0){
					tmpmap[ny][nx] = -1;
				}
				ny += dy[j];
				nx += dx[j];
			}
		}
	}
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (tmpmap[i][j] == 0) cnt++;
		}
	}
	return cnt;
}


void DFS(int cnt) {

	// 종료
	if (cnt >= ccnt) {
		// 다 골랐다.
		int res = Try_Watch();
		if (res < ans) ans = res;
		return;
	}

	// idx번을 고를 차례
	if (C[cnt].no == 2) { // 두 가지 경우의 수
		for (int i = 0; i < 2; i++) {
			sel[cnt] = i;
			DFS(cnt + 1);
		}
	}
	else if(C[cnt].no == 5){ // 한 가지
		sel[cnt] = 0;
		DFS(cnt + 1);
	}
	else {
		for (int i = 0; i < 4; i++) {
			sel[cnt] = i;
			DFS(cnt + 1);
		}
	}
}

int main(void) {
	Get_Input();
	DFS(0);
	printf("%d", ans);
	return 0;
}