BOJ : 15683 감시

 

사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다. 

CCTV의 최대 개수는 8개를 넘지 않는다.

출력

첫째 줄에 사각 지대의 최소 크기를 출력한다.

 

 

---

[BOJ 15683 (G5) 리뷰]

문제가 드럽게 길다..;

그런데 문제가 길다는것은 그만큼 설명을 자세하게 해준다는것.

정확히 뭘 구현해야하는지 제시해주고 있다.

 

사각지대의 최소 크기를 구해야하므로 백트래킹을 이용하여 모든경우를 탐색했다.

이런 류의 구현 문제는 별로 해본적이 없던터라 애를 먹었다. 코드도 엄청나게 길어졌다.

 

기본적으로 DFS를 구현한다음 각 CCTV의 종류에 맞게 DFS횟수와 방향을 조정해주었다.

 

코드 리팩토링은 언제나 귀찮다 ㅠ..

 

---

#include <iostream>
#include <queue>
#include <math.h>
#include <set>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

#define INF 987654321
#define X first
#define Y second

int r, c;
int board[8][8];
vector <pair<int, int>> CCTV;
stack <pair<int, int>> resetS;
int wallcnt=0;
int succnt = 0;
int minsize = INF;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };

void resetboard(int cnt)
{
	while (cnt--)
	{
		auto cur = resetS.top();
		resetS.pop();
		board[cur.X][cur.Y] = 0;
	}
}

int dfs(int dir,int x, int y)
{

	//0 right
	//1 down
	//2 left
	//3 up
	int count = 0;
	stack <pair<int, int>> S;
	S.push({ x,y });
	while (!S.empty())
	{
		auto cur = S.top(); S.pop();
		int nx = cur.X + dx[dir];
		int ny = cur.Y + dy[dir];
		if (nx < 0 || nx >= r || ny < 0 || ny >= c) break;
		if (board[nx][ny] == 6) break; //벽 만나면 탐색 종료
		if (board[nx][ny] != 0)
		{
			S.push({nx ,ny});
			continue;
		}
		board[nx][ny] = -1;
		count++;
		resetS.push({ nx,ny });
		S.push({ nx,ny });
	}

	return count;
}

void func(int index)
{
	if (index == CCTV.size())
	{
		int cnt = r * c - CCTV.size() - wallcnt - succnt;

		//cout << '\n';
		//for (int i = 0; i < r; i++)
		//{
		//	for (int j = 0; j < c; j++)
		//	{
		//		cout << board[i][j] << ' ';
		//	}
		//	cout << '\n';
		//}
		//cout << '\n';
		minsize = min(cnt, minsize);
		if (minsize == 0)
		{
			cout << minsize;
			exit(0);
		}
		return;
	}

	auto cur = CCTV[index];
	//CCTV의 종류에 따라 탐색다르게 해야함.
	int range = board[cur.X][cur.Y];
	switch (range)
	{
	case 1:
	{
		for (int i = 0; i < 4; i++)
		{
			int cnt = 0;
			cnt = dfs(i, cur.X, cur.Y);
			succnt += cnt;
			func(index + 1);
			succnt -= cnt;
			resetboard(cnt);
		}
		break;
	}
	case 2:
		for (int i = 0; i < 2; i++)
		{
			if (i == 0)
			{
				int cnt = 0;
				cnt += dfs(0, cur.X, cur.Y);
				cnt += dfs(2, cur.X, cur.Y);
				succnt += cnt;
				func(index + 1);
				succnt -= cnt;
				resetboard(cnt);
			}
			else
			{
				int cnt = 0;
				cnt += dfs(1, cur.X, cur.Y);
				cnt += dfs(3, cur.X, cur.Y);
				succnt += cnt;
				func(index + 1);
				succnt -= cnt;
				resetboard(cnt);
			}
		}
		break;
	case 3:
	{
		for (auto i : { 0,1,2 })
		{
			int cnt = 0;
			cnt += dfs(i, cur.X, cur.Y);
			cnt += dfs(i + 1, cur.X, cur.Y);
			succnt += cnt;
			func(index + 1);
			succnt -= cnt;
			resetboard(cnt);
		}
		int cnt = 0;
		cnt += dfs(3, cur.X, cur.Y);
		cnt += dfs(0, cur.X, cur.Y);
		succnt += cnt;
		func(index + 1);
		succnt -= cnt;
		resetboard(cnt);
		break;
	}
	case 4:
	{
		for (auto i : { 0,1 })
		{
			int cnt = 0;
			cnt += dfs(i, cur.X, cur.Y);
			cnt += dfs(i + 1, cur.X, cur.Y);
			cnt += dfs(i + 2, cur.X, cur.Y);
			succnt += cnt;
			func(index + 1);
			succnt -= cnt;
			resetboard(cnt);
		}
		int cnt = 0;
		cnt += dfs(2, cur.X, cur.Y);
		cnt += dfs(3, cur.X, cur.Y);
		cnt += dfs(0, cur.X, cur.Y);
		succnt += cnt;
		func(index + 1);
		succnt -= cnt;
		resetboard(cnt);

		cnt = 0;
		cnt += dfs(3, cur.X, cur.Y);
		cnt += dfs(0, cur.X, cur.Y);
		cnt += dfs(1, cur.X, cur.Y);
		succnt += cnt;
		func(index + 1);
		succnt -= cnt;
		resetboard(cnt);

	}
		break;
	case 5:
	{
		int cnt = 0;
		cnt += dfs(0, cur.X, cur.Y);
		cnt += dfs(1, cur.X, cur.Y);
		cnt += dfs(2, cur.X, cur.Y);
		cnt += dfs(3, cur.X, cur.Y);
		succnt += cnt;
		func(index + 1);
		succnt -= cnt;
		resetboard(cnt);
	}
		break;
	}

}


int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(0);
	
	cin >> r >> c;
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			cin >> board[i][j];
			if (board[i][j] > 0 && board[i][j] < 6) //CCTV의 좌표 벡터에 저장
				CCTV.push_back({ i,j });
			if (board[i][j] == 6) wallcnt++;
		}
	}

	func(0);
	cout << minsize;

}