[백준 15683번 C/C++] 감시

 

[백준 15683번 C/C++] 감시

 

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

15683번: 감시

---

 

해결전략

 

백트랙킹, Backtracking

---

 

 

코드

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 우, 상, 좌, 하
int dirY[4] = { 0, -1, 0, 1 };
int dirX[4] = { 1, 0, -1, 0 };

int n, m;
int answer = 2147000000;
vector<vector<int>> v, tmp;
vector<pair<int, int>> cctv;

void Check(int y, int x, int dir)
{
	dir %= 4;
	while(1){
		int ny = y + dirY[dir];
		int nx = x + dirX[dir];
		y = ny;
		x = nx;

		if (ny < 0 || n <= ny || nx < 0 || m <= nx) return;
		if (v[ny][nx] == 6) return;
		if (v[ny][nx] != 0) continue;
		v[ny][nx] = -1; // v[ny][ny]==0이면 -1로 변경
	}
}

void BackTracking(int k)
{
	if(k == cctv.size()){
		int cnt = 0;
		for (int y = 0; y < n; y++)
			for (int x = 0; x < m; x++)
				if (v[y][x] == 0) cnt++;

		answer = min(answer, cnt);
		return;
	}

	int y = cctv[k].first;
	int x = cctv[k].second;

	for(int dir=0; dir<4; dir++)
	{
		tmp = v;  // tmp 벡터를 v 벡터로 초기화

		if(v[y][x] == 1){
			Check(y, x, dir);
		}
		else if (v[y][x] == 2) {
			Check(y, x, dir);
			Check(y, x, dir + 2);
		}
		else if (v[y][x] == 3) {
			Check(y, x, dir);
			Check(y, x, dir + 1);
		}
		else if (v[y][x] == 4) {
			Check(y, x, dir);
			Check(y, x, dir + 1);
			Check(y, x, dir + 2);
		}
		else if (v[y][x] == 5) {
			Check(y, x, dir);
			Check(y, x, dir + 1);
			Check(y, x, dir + 2);
			Check(y, x, dir + 3);
		}

		BackTracking(k + 1);

		v = tmp; // case 종료이므로 초기화
	}
}

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

	cin >> n >> m;
	v.resize(n, vector<int>(m));
	tmp.resize(n, vector<int>(m));
    
	for(int y = 0; y < n; y++){
		for (int x = 0; x < m; x++) {
			cin >> v[y][x];
			if(0 < v[y][x] && v[y][x] < 6)
				cctv.push_back({ y, x });				
		}
	}

	BackTracking(0);
    
	cout << answer;

	return 0;
}

 

 

---