BOJ 15683 - 감시

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

문제

모든 조합을 살피고 시뮬레이션을 할 수 있어야 하는 문제.

CCTV가 보고 있는 방향을 하나씩 선택하면서, 모든 방향이 결정됐을 때 시뮬레이션 후 사각 지대의 개수를 구한다.
모든 조합을 살피다가 사각 지대의 개수가 최소가 되는 조합에서 정답을 출력하면 된다.

CCTV의 방향을 처리하는 시뮬레이션이 벽에서 막힌다거나 지도 밖으로 넘어가는 것 외에도 은근히 신경쓰이는 게 많다.
오목이나 틱택토류의 코드를 작성한 경험이 있다면 수월할 듯

상세한 부분을 제외하면 개략적인 구조는 이렇다.

	#define U (1<<0)
	#define R (1<<1)
	#define D (1<<2)
	#define L (1<<3)
	// i+1 == CCTV의 종류(1~5)
	// moving[i][j] := i번 종류의 CCTV가 j의 상태일 때, 보고있는 방향들
	vector<int> moving[5] = {
	{U, R, D, L},
	{U|D, R|L},
	{U|R, U|L, D|R, D|L},
	{U|R|L, D|R|L, R|U|D, L|U|D},
	{U|R|D|L}
	};
	int h, w, g[9][9];
	int solve(int cur) {
	if (/* 모든 CCTV의 방향이 결정됨 (한 가지 조합) */) {
	int temp[9][9]; // 원본을 건드리지 않고 사본(temp)을 사용
	memcpy(temp, g, sizeof(temp));
	// 각 CCTV를 결정된 방향대로 시뮬레이션
	// 이 조합으로 설치했을 때, 빈 칸의 개수
	int sum = 0;
	for (int i = 0; i < h; ++i)
	for (int j = 0; j < w; ++j)
	sum += temp[i][j] == 0;
	return sum;
	}
	int ret = INF;
	for (/* 현재 CCTV의 종류가 볼 수 있는 방향들 */) {
	// cur번째 CCTV는 i번 방향으로 결정
	direct[cur] = i;
	ret = min(ret, solve(cur + 1));
	}
	return ret;
	}

view raw boj-15683-psuedo.cpp hosted with ❤ by GitHub

여러 방향을 한번에 담아 처리하기 위해 비트로 각 방향을 표현했다. 비트가 겹치는 것을 확인하는 건 비트 AND연산으로 쉽게 구현할 수 있다. 예를 들어, 0010(2) AND 0111(2) 의 결과는 0010(2) 이므로 겹치는 부분이 있다. 0100(2) AND 0001(2) 는 0000(2)라서 겹치지 않는다.

전체 코드

	#include <bits/stdc++.h>
	using namespace std;
	using ii = pair<int, int>;
	const int INF = 0x3F3F3F3F;
	static int dx[] = { 0, 1, 0, -1 };
	static int dy[] = { -1, 0, 1, 0 };
	#define U (1<<0)
	#define R (1<<1)
	#define D (1<<2)
	#define L (1<<3)
	vector<int> moving[5] = {
	{U, R, D, L},
	{U|D, R|L},
	{U|R, U|L, D|R, D|L},
	{U|R|L, D|R|L, R|U|D, L|U|D},
	{U|R|D|L}
	};
	int h, w, g[9][9];
	int direct[10]; // 순서대로 등장한 cctv의 방향
	vector<int> cctv; // 순서대로 등장한 cctv의 종류
	vector<ii> cctvs; // 순서대로 등장한 cctv의 위치
	int solve(int cur) {
	if (cur == (int)cctv.size()) {
	int temp[9][9];
	memcpy(temp, g, sizeof(temp));
	for (int i = 0; i < (int)cctvs.size(); ++i) {
	int y = cctvs[i].first, x = cctvs[i].second;
	int type = cctv[i] - 1;
	for (int j = 0; j < 4; ++j) {
	if (moving[type][direct[i]] & (1 << j)) {
	for (int cy = y, cx = x;; cy += dy[j], cx += dx[j]) {
	if (cy < 0 || cy >= h || cx < 0 || cx >= w || temp[cy][cx] == 6) break;
	temp[cy][cx] = -1;
	}
	}
	}
	}
	int sum = 0;
	for (int i = 0; i < h; ++i)
	for (int j = 0; j < w; ++j)
	sum += temp[i][j] == 0;
	return sum;
	}
	int ret = INF;
	for (int i = 0; i < (int)moving[cctv[cur] - 1].size(); ++i) {
	direct[cur] = i;
	ret = min(ret, solve(cur + 1));
	}
	return ret;
	}
	int main() {
	scanf("%d %d", &h, &w);
	for (int i = 0; i < h; ++i) {
	for (int j = 0; j < w; ++j) {
	scanf("%d", &g[i][j]);
	if (1 <= g[i][j] && g[i][j] <= 5) {
	cctv.push_back(g[i][j]);
	cctvs.push_back(make_pair(i, j));
	}
	}
	}
	printf("%d\n", solve(0));
	return 0;
	}

view raw boj-15683.cpp hosted with ❤ by GitHub