[백준 15683] 감시

문제 링크 => https://www.acmicpc.net/problem/15683

15683번: 감시

---

삼성 역량 테스트 문제로 시뮬레이션 문제이다.

 

감시 케이스는 총 5가지로 다음과 같다.

 

(1) 한 쪽 방향으로 상하좌우 총 4번 감독할 수 있는 경우

(2) 두 쪽 방향으로 상하 or 좌우 방향으로 2번을 감독할 수 있는 경우

(3) 두 쪽 방향으로 감시하는 방향이 직각인 방향으로 총 4번 감독할 수 있는 경우

(4) 세 쪽 방향으로 총 4번 감독할 수 있는 경우

(5) 모든 방향으로 딱 한번 감독할 수 있는 경우

 

처음으로 감시할 수 있는 CCTV 에 대한 좌표들을 저장하기 위해 벡터를 선언하여 push_back을 해준다.

 

그리고 CCTV 의 총 갯수를 n 이라고 하고 감시할 때 케이스 별로 나눠서 접근해야 한다. (1번 CCTV 부터 5번 CCTV 까지 전부 다르게 감시)

 

첫 번째 CCTV 가 감시한 경우 => 두 번째 CCTV 가 감시한 경우 => ... => n 번째 CCTV 가 감시한 경우

 

즉, n 번째까지 모든 감시가 완료한 경우 남아있는 사무실에 빈칸의 갯수를 구할 수 있다.

 

주의해야 할 점은 n 번째 CCTV 가 감시를 완료하고 (n-1) 번째 CCTV 로 넘어가는 과정에서 n 번째 CCTV 가 감시한 영역만을 빈칸으로 설정해야 한다.

 

즉, i 번째 CCTV가 감시할 때 감시한 영역을 저장할 수 있도록 임의의 벡터를 설정해야 한다.

 

풀이 Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#define INF 1000000000
#define endl '\n'

using namespace std;

int N, M;
int Map[8][8];
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
vector<pair<int, int>> monitorV;

void input() {

	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] <= 5) monitorV.push_back({ i,j });
		}
	}

}

void monitor(int startX, int startY, int direction, vector<pair<int, int>>& v) {
	queue<pair<int, int>> Q;
	Q.push({ startX,startY });

	while (!Q.empty()) {
		int x = Q.front().first, y = Q.front().second;
		Q.pop();

		int nextX = x + dx[direction], nextY = y + dy[direction];
		if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= M
			|| Map[nextX][nextY] == 6) continue;

		if (Map[nextX][nextY] == 0) {
			Map[nextX][nextY] = 9;
			v.push_back({ nextX,nextY });
		}
		Q.push({ nextX,nextY });
	}
}

int solve(int n) {

	if (n == monitorV.size()) {
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				cnt += (Map[i][j] == 0 ? 1 : 0);
			}
		}
		return cnt;
	}

	vector<pair<int, int>> v;
	int x = monitorV[n].first, y = monitorV[n].second, ret = INF;
	switch (Map[x][y]) {
	case 1:
		for (int i = 0; i < 4; i++) {
			v.clear();
			monitor(x, y, i, v);
			ret = min(ret, solve(n + 1));
			for (int j = 0; j < v.size(); j++) Map[v[j].first][v[j].second] = 0;
		}
		break;
	case 2:
		for (int i = 0; i < 2; i++) {
			v.clear();
			monitor(x, y, i, v), monitor(x, y, i + 2, v);
			ret = min(ret, solve(n + 1));
			for (int j = 0; j < v.size(); j++) Map[v[j].first][v[j].second] = 0;
		}
		break;
	case 3:
		for (int i = 0; i < 4; i++) {
			v.clear();
			monitor(x, y, i, v), monitor(x, y, (i + 1) % 4, v);
			ret = min(ret, solve(n + 1));
			for (int j = 0; j < v.size(); j++) Map[v[j].first][v[j].second] = 0;
		}
		break;
	case 4:
		for (int i = 0; i < 4; i++) {
			v.clear();
			monitor(x, y, i, v), monitor(x, y, (i + 1) % 4, v), monitor(x, y, (i + 2) % 4, v);
			ret = min(ret, solve(n + 1));
			for (int j = 0; j < v.size(); j++) Map[v[j].first][v[j].second] = 0;
		}
		break;
	case 5:
		for (int i = 0; i < 4; i++) monitor(x, y, i, v);
		ret = min(ret, solve(n + 1));
		for (int j = 0; j < v.size(); j++) Map[v[j].first][v[j].second] = 0;
		break;
	}

	return ret;
}

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

	input();
	cout << solve(0);

	return 0;
}