백준 15683번 감시 (c++)

 

골드 2 이상의 문제에 지쳐버린 나머지 결국 골드3으로 돌아왔다

당분간 골드3 수준에서 여러 알고리즘을 익히는 방향으로 공부하려 한다.

 

본래 이런 백트랙킹 문제는 방문을 체크하는 배열에 이번 재귀의 방문을 체크하고 재귀 후 체크를 해제하는 식으로 풀기마련인데,

이렇게 공간을 돌아다니는 문제는 체크해제가 매우 까다로워지므로 매 방문마다 체크 배열을 새로 만들어 쓰는편이 편하다

 

signed main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		vector<int> tmp;
		for (int j = 0; j < m; j++)
		{
			int a;
			cin >> a;
			tmp.push_back(a);
			if (a != 0 && a != 6)
			{
				cctv.push_back({ j,i });
			}
		}
		arr.push_back(tmp);
	}
	sol(arr, 0);
	cout << ans << endl;

}

백트래킹 함수에 배열을 편하게 전달할 수 있도록 이중 vector를 사용했다.

굳이 이중for문으로 돌아다니며 CCTV의 위치를 체크할 필요 없게하기 위해 CCTV의 좌표를 따로 배열에 저장했다.

 

void sol(vector<vector<int>> checker,int idx)
{
	if (idx >= cctv.size())
	{
		ans = min(ans, sizecheck(checker));
	}
	else
	{
		for (int i = 0; i < 4; i++)
		{
			vector<vector<int>> tmp = checker;
			pair<int, int> point = cctv[idx];
			int camera = arr[point.second][point.first];

			if (camera == 1)
			{
				marker(tmp, dir(i), point.first, point.second);
			}
			else if (camera == 2)
			{
				marker(tmp, dir(i), point.first, point.second);
				marker(tmp, dir(i+2), point.first, point.second);
			}
			else if (camera == 3)
			{
				marker(tmp, dir(i), point.first, point.second);
				marker(tmp, dir(i+1), point.first, point.second);
			}
			else if (camera == 4)
			{
				marker(tmp, dir(i), point.first, point.second);
				marker(tmp, dir(i+1), point.first, point.second);
				marker(tmp, dir(i+2), point.first, point.second);
			}
			else if (camera == 5)
			{
				marker(tmp, dir(i), point.first, point.second);
				marker(tmp, dir(i+1), point.first, point.second);
				marker(tmp, dir(i+2), point.first, point.second);
				marker(tmp, dir(i+3), point.first, point.second);
			}

			sol(tmp, idx + 1);
		}
	}
}

idx는 현재 재귀에서 몇번째 CCTV를 검사하고 있는지 나타낸다.

모든 CCTV를 체크했으면 한 판이 만들어진것이므로 

sizecheck() 함수에서 빈칸이 몇칸인지 세준다

 

CCTV는 사방으로 돌릴 수 있으므로 4방향을 모두 따로 세줄 것이다.

물론 특정 방향은 의미가 없는 위치나, CCTV의 종류가 있지만 따로 고려해주지는 않았다.

 

void marker(vector<vector<int>>& checker, int way, int x, int y)
{
	while (true)
	{
		x += mx[way];
		y += my[way];
		if (x < 0 || x >= m || y < 0 || y >= n) break;
		if (arr[y][x] == 6) break;
		checker[y][x] = -1;
	}
}

지금도 코드가 길긴하지만 정말 지나치게 길어지는것을 방지하기위해 한방향으로 쭉 긋는 부분은 함수로 분리해줬다

지정된 방향으로 벽이 나오거나 범위를 벗어나기전까지 체크배열을 채워준다

 

int dir(int way)
{
	if (way < 0)
	{
		return way + 4;
	}
	else if (way >= 4)
	{
		return way - 4;
	}
	else return way;
}

방향표기의 편의성을 위해 숫자를 0~3 사이로 만들어주는 기능을 만들어 써줬다.

 

 

 

전체코드

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#define ll long long int
using namespace std;

int n, m;
vector<vector<int>> arr;
vector<pair<int, int>> cctv;
int mx[4] = { 1,0,-1,0 };
int my[4] = { 0,-1,0,1 };
int ans = 210000000;
int sizecheck(vector < vector<int>> &checker)
{
	int cnt = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (checker[i][j] == 0) cnt++;
		}
	}
	return cnt;
}

void marker(vector<vector<int>>& checker, int way, int x, int y)
{
	while (true)
	{
		x += mx[way];
		y += my[way];
		if (x < 0 || x >= m || y < 0 || y >= n) break;
		if (arr[y][x] == 6) break;
		checker[y][x] = -1;
	}
}

int dir(int way)
{
	if (way < 0)
	{
		return way + 4;
	}
	else if (way >= 4)
	{
		return way - 4;
	}
	else return way;
}

void sol(vector<vector<int>> checker,int idx)
{
	if (idx >= cctv.size())
	{
		ans = min(ans, sizecheck(checker));
	}
	else
	{
		for (int i = 0; i < 4; i++)
		{
			vector<vector<int>> tmp = checker;
			pair<int, int> point = cctv[idx];
			int camera = arr[point.second][point.first];

			if (camera == 1)
			{
				marker(tmp, dir(i), point.first, point.second);
			}
			else if (camera == 2)
			{
				marker(tmp, dir(i), point.first, point.second);
				marker(tmp, dir(i+2), point.first, point.second);
			}
			else if (camera == 3)
			{
				marker(tmp, dir(i), point.first, point.second);
				marker(tmp, dir(i+1), point.first, point.second);
			}
			else if (camera == 4)
			{
				marker(tmp, dir(i), point.first, point.second);
				marker(tmp, dir(i+1), point.first, point.second);
				marker(tmp, dir(i+2), point.first, point.second);
			}
			else if (camera == 5)
			{
				marker(tmp, dir(i), point.first, point.second);
				marker(tmp, dir(i+1), point.first, point.second);
				marker(tmp, dir(i+2), point.first, point.second);
				marker(tmp, dir(i+3), point.first, point.second);
			}

			sol(tmp, idx + 1);
		}
	}
}

signed main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		vector<int> tmp;
		for (int j = 0; j < m; j++)
		{
			int a;
			cin >> a;
			tmp.push_back(a);
			if (a != 0 && a != 6)
			{
				cctv.push_back({ j,i });
			}
		}
		arr.push_back(tmp);
	}
	sol(arr, 0);
	cout << ans << endl;

}