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

문제

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.

1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.

CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.

CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0

지도에서 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호이다. 위의 예시에서 1번의 방향에 따라 감시할 수 있는 영역을 '#'로 나타내면 아래와 같다.

// →			// ←			// ↑			// ↓
0 0 0 0 0 0		0 0 0 0 0 0		0 0 # 0 0 0		0 0 0 0 0 0
0 0 0 0 0 0		0 0 0 0 0 0		0 0 # 0 0 0		0 0 0 0 0 0
0 0 1 # 6 0		# # 1 0 6 0		0 0 1 0 6 0		0 0 1 0 6 0
0 0 0 0 0 0		0 0 0 0 0 0		0 0 0 0 0 0		0 0 # 0 0 0

CCTV는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때는 6의 오른쪽에 있는 벽을 감시할 수 없다.

0 0 0 0 0 0
0 2 0 0 0 0
0 0 0 0 6 0
0 6 0 0 2 0
0 0 0 0 0 0
0 0 0 0 0 5

위의 예시에서 감시할 수 있는 방향을 알아보면 아래와 같다.

// 왼쪽 상단 2: ↔		// 왼쪽 상단 2: ↔		// 왼쪽 상단 2: ↕		// 왼쪽 상단 2: ↕
// 오른쪽 하단 2: ↔	// 오른쪽 하단 2: ↕	// 오른쪽 하단 2: ↔	// 오른쪽 하단 2: ↕
0 0 0 0 0 #		0 0 0 0 0 #		0 # 0 0 0 #		0 # 0 0 0 #
# 2 # # # #		# 2 # # # #		0 2 0 0 0 #		0 2 0 0 0 #
0 0 0 0 6 #		0 0 0 0 6 #		0 # 0 0 6 #		0 # 0 0 6 #
0 6 # # 2 #		0 6 0 0 2 #		0 6 # # 2 #		0 6 0 0 2 #
0 0 0 0 0 #		0 0 0 0 # #		0 0 0 0 0 #		0 0 0 0 # #
# # # # # 5		# # # # # 5		# # # # # 5		# # # # # 5

CCTV는 CCTV를 통과할 수 있다. 아래 예시를 보자.

0 0 2 0 3
0 6 0 0 0
0 0 6 6 0
0 0 0 0 0

위와 같은 경우에 2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.

# # 2 # 3
0 6 # 0 #
0 0 6 6 #
0 0 0 0 #

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

 

입력

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

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

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

 

출력

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

 

코드

#include <iostream>
#include <string>
#include <vector>
#include <set>

using namespace std;

struct pos
{
	int r;
	int c;
	string d;

	void init(int r, int c, string d)
	{
		this->r = r;
		this->c = c;
		this->d = d;
	}
};

int N;
int M;
int answer;		// 사각 지대의 최솟값
vector<pos> cctv;	// CCTV의 위치와 감시 방향

// 범위 내인지 확인
bool in_range(int r, int c)
{
	if (r < 0 || r >= N || c < 0 || c >= M)
		return false;
	return true;
}

// 새로운 벡터를 할당하고 p에 위치한 CCTV가 감시하는 영역을 표시하여 리턴
vector< vector<int> > find_area(pos p, vector< vector<int> > &office)
{
	int i, nr, nc, num;
	int dr[] = {-1, 0, 1, 0};
	int dc[] = {0, 1, 0, -1};
	vector< vector<int> > res;

	// CCTV의 유형 번호
	num = office[p.r][p.c];
	// 사무실의 상태를 복사
	res.assign(office.begin(), office.end());
	// 모든 방향에 대하여
	for (i = 0; i < 4; i++)
	{
		// 감시하지 않는 방향인 경우 패스
		if (p.d[i] == '0')
		{
			continue;
		}
		nr = p.r;
		nc = p.c;
		// 해당 방향에 대하여 감시할 수 있는 칸을 표시
		while (1)
		{
			nr += dr[i];
			nc += dc[i];
			// 범위를 벗어나거나 벽을 만나면 중단
			if (!in_range(nr, nc) || res[nr][nc] == 6)
				break;
			res[nr][nc] = num;
		}
	}
	return res;
}

// 사각지대의 크기를 확인 (office[i][j] == 0인 경우)
int count_blind(vector< vector<int> > &office)
{
	int i, j, res = 0;

	for (i = 0; i < N; i++)
	{
		for (j = 0; j < M; j++)
		{
			if (!office[i][j])
				res++;
		}
	}
	return res;
}

// idx번째 CCTV가 감시할 수 있는 모든 경우를 확인
void dfs(int idx, vector< vector<int> > office)
{
	pos p;
	set<string> check;

	// 모든 CCTV를 확인했다면 사각지대의 크기를 확인해 최솟값으로 갱신
	if (idx == cctv.size())
	{
		answer = min(answer, count_blind(office));
		return;
	}
	// idx번째 CCTV를 회전시키며 모든 경우를 확인
	p = cctv[idx];
	while (1)
	{
		// 이미 확인한 조건인 경우 중단
		if (check.find(p.d) != check.end())
			return;
		// check에 삽입해 확인했음을 표시
		check.insert(p.d);
		// 다음 CCTV에 대하여 dfs 수행
		dfs(idx + 1, find_area(p, office));
		// CCTV 회전 (반시계 방향)
		p.d = p.d.substr(1) + p.d.front();
	}
}

int main()
{
	int i, j, num;
	pos p;
	string dir[] = {"", "1000", "1010", "1100", "1110", "1111"};
	vector< vector<int> > office;

	cin >> N >> M;
	office.resize(N, vector<int> (M));
	answer = N * M;
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < M; j++)
		{
			cin >> office[i][j];
			num = office[i][j];
			if (num > 0 && num < 6)
			{
				p.init(i, j, dir[num]);
				cctv.push_back(p);
			}
		}
	}
	dfs(0, office);
	cout << answer << endl;
	return 0;
}

 

사무실의 크기로 answer를 초기화하고 dfs를 통해 CCTV의 유형에 따라 다음과 같은 순서로 모든 경우를 확인한다. 

CCTV가 감시하는 칸에 해당 CCTV의 유형 번호(1~5)를 저장하기 때문에 모든 CCTV를 확인한 후 빈칸(0)인 곳이 사각지대이다. 배열 dr, dc와 문자열 d에서 0번 인덱스는 북쪽, 1번 인덱스는 동쪽, 2번 인덱스는 남쪽, 3번 인덱스는 서쪽을 의미한다. 문자열 d[i]의 값이 1이면 해당 방향을 감시한다는 의미이다. 또한 배열 dir에서 각 인덱스는 CCTV의 유형 번호를 의미한다. 

 

링크

15683번: 감시

inbdni/Baekjoon