[백준 15683] 감시

문제 바로가기

15683번: 감시

청소년 상어 문제 풀면서 제대로 안 읽었다가 호되게 당한 기억이 있어서..

이번 문제는 풀기 전에 충분히 생각하고 풀었다.

 

문제를 풀다보니 대충 생각하고 무작정 코드부터 짜면 로직이 꼬이거나 실수가 많아져서 결국은 시간이 더 오래걸린다는 것을 체득했다.

그래서 ! 이젠 확실히 문제를 이해할 때까지 아이패드에 적어보고 문제에서 요구하는 사항을 완벽히 이해하고 푸는 연습중이다. 이렇게 하니 코드 짜면서 헷갈릴 일이 적어서 오히려 더 빨리 풀 수 있는 것 같다.

 

이 문제도 읽고나서 어떻게 풀어야 할까 고민을 많이 했는데 나는 백트래킹으로 구현을 했다.

cctv의 좌표는 cctv 벡터에 저장했고, dfs 함수에서 cctv가 감시할 수 있는 경우를 for문에서 구해주었다. cctv가 어느 방향을 감시한 후에 그 다음 cctv로 옮겨가서 똑같은 방법으로 수행한다. (재귀 호출)

dfs 함수의 인자인 order == cctv.size()라면, 모든 cctv를 다 봤기 때문에 재귀함수를 빠져나온다. 이 때 사각지대 영역을 계산하고, 현재까지의 min_empty값 보다 작다면 min_empty를 갱신한다.

재귀함수를 빠져나온 이후에는 다시 원래 상태로 돌려주기 위해 copy_map() 함수를 사용했다.

 

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int pos[4][2] = { {-1,0},{0,1},{1,0},{0,-1} }; //위, 오른쪽, 아래, 왼쪽
int map[8][8];
int N, M;
int seen[8][8];
int min_empty = 64;
vector<pair<int, int>> cctv;

bool isIn(int x, int y)
{
	if (x >= 0 && x < M && y >= 0 && y < N)
		return true;
	return false;
}
void make_path(int x, int y, int dir)
{
	int nx = x + pos[dir][1];
	int ny = y + pos[dir][0];

	while (isIn(nx, ny) && map[ny][nx] != 6)
	{
		seen[ny][nx] = 1;

		nx = nx + pos[dir][1];
		ny = ny + pos[dir][0];
	}
	
}

void copy_map(int original[8][8], int neww[8][8])
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
			neww[i][j] = original[i][j];
	}
}

int find_empty()
{
	int sum = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (seen[i][j] == 0)
				sum++;
		}
	}

	return sum;
}
void dfs(int order)
{
	if (order == cctv.size())
	{
		min_empty = min(min_empty, find_empty());
		return;
	}

	int cy = cctv[order].first;
	int cx = cctv[order].second;
	int c_menu = map[cctv[order].first][cctv[order].second];

	int new_seen[8][8];
	copy_map(seen, new_seen);
		
	if (c_menu == 1)
	{
		for (int i = 0; i < 4; i++)
		{
			make_path(cx, cy, i);
			dfs(order + 1);
			copy_map(new_seen, seen);
		}
	}
	else if (c_menu == 2)
	{
		make_path(cx, cy, 0);
		make_path(cx, cy, 2);
		dfs(order + 1);
		copy_map(new_seen, seen);

		make_path(cx, cy, 1);
		make_path(cx, cy, 3);
		dfs(order + 1);
		copy_map(new_seen, seen);
	}
	else if (c_menu == 3)
	{
		for (int i = 0; i < 4; i++)
		{
			make_path(cx, cy, i);
			make_path(cx, cy, (i + 1) % 4);
			dfs(order + 1);
			copy_map(new_seen, seen);
		}
	}
	else if (c_menu == 4)
	{
		for (int i = 0; i < 4; i++)
		{
			make_path(cx, cy, i);
			make_path(cx, cy, (i + 1) % 4);
			make_path(cx, cy, (i + 2) % 4);
			dfs(order + 1);
			copy_map(new_seen, seen);
		}
	}
	else if (c_menu == 5)
	{
		for (int i = 0; i < 4; i++)
		{
			make_path(cx, cy, i);
		}
		dfs(order + 1);
		copy_map(new_seen, seen);
	}
}

int main()
{
	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] < 6)
			{
				seen[i][j] = 1;
				cctv.push_back({ i, j });
			}
			else if (map[i][j] == 6)
				seen[i][j] = 1;
				
		}
	}

	dfs(0);

	cout << min_empty << endl;

	return 0;

}