백준(BOJ) 15683번 감시

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

15683번: 감시

 

풀이 : v배열에 1~5 cctv인 좌표 y,x들을 담는다. 그 후 재귀호출을 통해 0이 최소가 되는 best를 찾는다.

 

solve 함수는 해당 좌표에 90도씩 돌려주면서 재귀적으로 solve를 호출하고

 

rotate 함수는 그 i번 돌려( i는 한번에 90도 ) 주는 함수이다. 

 

	#include <iostream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	int N, M;
	int room[9][9];
	int visited[9][9];
	vector<pair<int, int>> v;
	//상우하좌
	const int dy[4] = { -1,0,1,0 };
	const int dx[4] = { 0,1,0,-1 };
	int best = 987654321;
	void check(int y, int x, int i, int num)
	{
	int ny = y ;
	int nx = x ;
	while (1) {
	ny += dy[i];
	nx += dx[i];
	if (room[ny][nx] == 6) break;
	if (!(ny >= 0 && ny < N && nx >= 0 && nx < M)) break;
	visited[ny][nx] += num;
	}
	}
	void rotate(int begin, int i, int num)
	{
	int y = v[begin].first;
	int x = v[begin].second;
	int number = room[y][x];
	if (number == 1)
	{
	// 오른쪽
	check(y, x, (i+1)%4, num);
	}
	else if (number == 2)
	{
	int y2 = y;
	int x2 = x;
	// 오른쪽 꺼
	check(y, x, (i + 1)%4, num);
	// 왼쪽 꺼
	check(y, x, (i + 3) % 4, num);
	}
	else if (number == 3)
	{
	// 오른쪽 꺼
	check(y, x, (i + 1) % 4, num);
	// 위쪽꺼 꺼
	check(y, x, (i + 0) % 4, num);
	}
	else if (number == 4)
	{
	// 오른쪽 꺼
	check(y, x, (i + 1) % 4, num);
	// 위쪽꺼 꺼
	check(y, x, (i + 0) % 4, num);
	//왼쪽꺼
	check(y, x, (i + 3) % 4, num);
	}
	else if (number == 5) {
	// 오른쪽 꺼
	check(y, x, (i + 1) % 4, num);
	// 위쪽꺼 꺼
	check(y, x, (i + 0) % 4, num);
	//왼쪽꺼
	check(y, x, (i + 3) % 4, num);
	// 아래꺼
	check(y, x, (i + 2) % 4, num);
	}
	}
	void solve(int begin)
	{
	if (begin > v.size() - 1) {
	int cnt = 0;
	for (int i = 0; i < N; ++i) {
	for (int j = 0; j < M; ++j) {
	if (visited[i][j] == 0)
	cnt++;
	}
	}
	best = min(best, cnt);
	return;
	}
	for (int i = 0; i < 4; ++i)
	{
	rotate(begin, i, 1);
	solve(begin + 1);
	rotate(begin, i, -1);
	}
	}
	int main()
	{
	cin >> N >> M;
	for (int i = 0; i < N; ++i) {
	for (int j = 0; j < M; ++j) {
	cin >> room[i][j];
	if (room[i][j] != 0 && room[i][j] != 6)
	{
	v.push_back({ i,j });
	visited[i][j] = room[i][j];
	}
	if (room[i][j] == 6)
	visited[i][j] = 6;
	}
	}
	// 담을 y,x 좌표가 없을때
	if (v.size() == 0)
	{
	int cnt = 0;
	for (int i = 0; i < N; ++i)
	for (int j = 0; j < M; ++j)
	if (room[i][j] == 0)
	cnt++;
	cout << cnt << "\n";
	return 0;
	}
	else {
	solve(0);
	cout << best << "\n";
	}
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub