[백준 15683번] 감시 C++

[15683번 감시]
https://www.acmicpc.net/problem/15683

DFS를 이용한 완전탐색 구현 문제였다. 아이디어는 간단했지만 구현이 쉽지 않아서 시간을 많이 소모했다.

풀이 방법

1.

DFS로 큰 틀을 잡는 게 우선인 것 같다.
처음에 입력을 받을 때 첫 번째 카메라, 두 번째 카메라, ... 이런 식으로 최대 여덟 번째 카메라까지 입력을 받을 수 있다(편의상 1번, 2번, ..., 8번으로 칭하겠다. 문제의 카메라 타입과 헷갈리지 않길 바란다).

카메라를 2개 입력 받았다고 예를 들어보겠다.

(depth == 0)	
트리 형식으로 1번 카메라의 첫 번째 방향으로 감시한 구역을 표시하고,

  (depth == 1)
  다시 dfs를 타고 한 층 들어가서 2번 카메라의 첫 번째 방향으로
  감시한 구역을 표시한다. 이 때 사각지대의 개수를 세고,
  현재 사각지대의 개수보다 적으면 갱신해준다.

(depth == 0)
그 이후에는 depth가 1인 층을 빠져나오면서
2번 카메라가 감시했던 구역을 감시되지 않은 구역으로 다시 바꿔주는 게 중요하다.
	
    (depth == 1)
    다시 dfs를 타고 한 층 들어가서 2번 카메라의 두 번째 방향으로
    감시한 구역을 표시한다. 사각지대의 개수를 갱신해준다.
    
(depth == 0)
depth 1을 빠져나오면서, 2번 카메라의 감시 방향이 끝났기 때문에
1번 카메라의 두 번째 감시 방향부터 1번 카메라의 감시 방향이 끝날 때까지
위와 같은 방식으로 반복한다.

트리 그림으로 나타내면 이런 식이다.

주어진 카메라가 3대이고, 각각의 타입이 4 / 2 / 4라면,

이런 식으로 dfs를 통해 완전탐색을 구현하면 된다. 마지막 층에서 한 층 더 깊이 들어가게 되어 depth가 카메라의 개수와 일치하게 될 때 사각지대를 세어준 후, 현재의 최소값보다 작다면 최소값을 갱신해준다.

2.

check라는 2차원 배열을 room 배열의 크기만큼 매번 dfs를 실행할 때 초기화시켜주고, 카메라가 비어있던 사각지대를 감시했다면 감시한 표시를 해준다(이전에 카메라의 감시 구역과 현재 카메라의 감시 구역이 겹칠 수 있기 때문에 현재 카메라가 새로 감시한 구역만을 저장해둬야 하기 때문이다).

dfs가 끝나고 한 층을 다시 올라오면 표시해둔 새로 감시된 구역만 골라서 room 배열에서 지워준다.

c++ 코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>  // pair
#include <tuple>
#include <stack>
#define ll long long
#define INF 1e9
using namespace std;

int ans = 987654321;
int n, m;
int room[9][9];
int cctv;
int cctvs[8] = {0,};  // cctv direction
int cctvDir[6] = {0,4,2,4,4,1};
pair<int,int> coord[6][8];

int count() {
	int cnt = 0;
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=m;++j) {
			if(room[i][j] == 0)
				cnt++;
		}
	}

	return cnt;
}

void checkUp(int r, int c, int checked[9][9]) {
	for(int i=r;i>=1;--i) {
		if(room[i][c] == 6) break;
		else if(room[i][c] == 0) {
			room[i][c] = 1;
			checked[i][c] = 9;
		}
	}

	return;
}

void checkDown(int r, int c, int checked[9][9]) {
	for(int i=r;i<=n;++i) {
		if(room[i][c] == 6) break;
		else if(room[i][c] == 0) {
			room[i][c] = 1;
			checked[i][c] = 9;
		}
	}

	return;
}

void checkLeft(int r, int c, int checked[9][9]) {
	for(int j=c;j>=1;--j) {
		if(room[r][j] == 6) break;
		else if(room[r][j] == 0) {
			room[r][j] = 1;
			checked[r][j] = 9;
		}
	}

	return;
}

void checkRight(int r, int c, int checked[9][9]) {
	for(int j=c;j<=m;++j) {
		if(room[r][j] == 6) break;
		else if(room[r][j] == 0) {
			room[r][j] = 1;
			checked[r][j] = 9;
		}
	}
}

void camera1(int dir, int checked[9][9], int order) {

	pair<int,int> p = coord[1][order];
	int r = p.first;
	int c = p.second;

	switch(dir) {
		case 0:
			checkUp(r, c, checked);
			break;

		case 1:
			checkRight(r, c, checked);
			break;

		case 2:
			checkDown(r, c, checked);
			break;

		case 3:
			checkLeft(r, c, checked);
			break;
	}

	return;
}

void camera2(int dir, int checked[9][9], int order) {

	pair<int,int> p = coord[2][order];
	int r = p.first;
	int c = p.second;

	switch(dir) {
		case 0:
			checkRight(r, c, checked);
			checkLeft(r, c, checked);

			break;

		case 1:
			checkUp(r, c, checked);
			checkDown(r, c, checked);

			break;
	}

	return;
}

void camera3(int dir, int checked[9][9], int order) {

	pair<int,int> p = coord[3][order];
	int r = p.first;
	int c = p.second;

	switch(dir) {
		case 0:
			checkUp(r,c,checked);
			checkRight(r,c,checked);
			break;

		case 1:
			checkRight(r,c,checked);
			checkDown(r,c,checked);
			break;

		case 2:
			checkDown(r,c,checked);
			checkLeft(r,c,checked);
			break;

		case 3:
			checkLeft(r,c,checked);
			checkUp(r,c,checked);
			break;
	}

	return;
}

void camera4(int dir, int checked[9][9], int order) {

	pair<int,int> p = coord[4][order];
	int r = p.first;
	int c = p.second;

	switch(dir) {
		case 0:
			checkLeft(r,c,checked);
			checkUp(r,c,checked);
			checkRight(r,c,checked);
			break;

		case 1:
			checkUp(r,c,checked);
			checkRight(r,c,checked);
			checkDown(r,c,checked);
			break;

		case 2:
			checkRight(r,c,checked);
			checkDown(r,c,checked);
			checkLeft(r,c,checked);
			break;

		case 3:
			checkDown(r,c,checked);
			checkLeft(r,c,checked);
			checkUp(r,c,checked);
			break;
	}
	return;
}

void camera5(int dir, int checked[9][9], int order) {

	pair<int,int> p = coord[5][order];
	int r = p.first;
	int c = p.second;

	checkUp(r,c,checked);
	checkDown(r,c,checked);
	checkLeft(r,c,checked);
	checkRight(r,c,checked);

	return;
}



void camera(int type, int dir, int checked[9][9], int order) {
	switch(type) {
		case 1:
			camera1(dir, checked, order);
			break;

		case 2:
			camera2(dir, checked, order);
			break;

		case 3:
			camera3(dir, checked, order);
			break;

		case 4:
			camera4(dir, checked, order);
			break;

		case 5:
			camera5(dir, checked, order);
			break;
	}
}

void view(int type, int dir, int checked[9][9], int order) {
	camera(type, dir, checked, order);

	return;
}

void unView(int type, int dir, int checked[9][9]) {
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=m;++j) {
			if(checked[i][j] == 9) {
				room[i][j] = 0;
			}
		}
	}
	return;
}

void dfs(int depth) {
	if(depth == cctv) {
		int cnt = count();
		ans = min(ans, cnt);

		return;
	}

	int order = depth;
	int type = cctvs[order];
	int dir = cctvDir[type];
	for(int i=0;i<dir;++i) {
		int checked[9][9];
		memset(checked, 0, sizeof(checked));

		view(type, i, checked, order);
		dfs(depth + 1);

		unView(type, i, checked);
	}

	return;
}


int main(void) {
	ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

	cin >> n >> m;
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=m;++j) {
			cin >> room[i][j];
			if(1 <= room[i][j] && room[i][j] <= 5) {
				cctvs[cctv] = room[i][j];
				coord[room[i][j]][cctv] = make_pair(i,j);
				cctv++;
			}
		}
	}

	dfs(0);

	cout << ans << '\n';
	
	return 0;
}

코드가 불필요하게 길어진 감이 없지 않다. 조금 더 효율적으로 코드를 짜는 법을 연습해야할 것 같다.