문제

문제 링크

해설

• N x M은 최대 8 x 8이고 CCTV의 개수는 최대 8개이므로 모든 경우의 수를 탐색하는 전형적인 bruteforce 시뮬레이션 + 재귀(DFS) 문제입니다.
• 다만, 조금 까다로운 점은 CCTV를 회전하는 연산이 포함돼있다는 점입니다.
• CCTV 종류(1, 2, 3, 4, 5번)에 따라 4방향 회전을 고려해야하며,
  • 2번 CCTV는 2번 회전 == 4번 회전이고, 1번 회전 == 3번 회전이며
  • 5번 CCTV는 회전이 의미가 없습니다.

void DFS(int idx){
	if (idx == cctv.size()) {
		int cnt = 0;
		for (int y = 0; y < N; ++y)
			for(int x = 0; x < M; ++x)
				if (office[y][x] == 0) cnt++;
		answer = min(answer, cnt);
		return;
	}
	for(int d = 0; d < 4; ++d) {
		vector<pair<int, int>> changedPos = watch(idx, d); 
		DFS(idx + 1);
		for (const auto& pos : changedPos) 
            office[pos.first][pos.second] = 0; 
	}
}

• 각 cctv마다 4방향으로 돌면서 감시를 시작합니다. 이때, watch() 함수를 호출해서 감시(State::WATCH) 표시한 곳의 좌표를 반환받습니다.
• 왜냐하면, 다른 경우의 수(다르게 회전한 경우)를 고려하기 위해서는 기존에 감시표시한 곳을 다시 빈칸으로 초기화해야 하기 때문입니다.

코드

#include <bits/stdc++.h>
using namespace std;

constexpr int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
constexpr int WATCHED = 8;

int N, M, office[10][10], answer = 64; 
vector<pair<int, int>> cctv;

inline bool isValidPos(int y, int x) {
	return (0 <= y && y <= N) && (0 <= x && x <= M);
}

vector<pair<int, int>> watch(int here, int dir){
	vector<pair<int, int>> ret;
	int y = cctv[here].first;
	int x = cctv[here].second;
	
	if (office[y][x] == 1) {
		while (true){
			int ny = y + d[dir][0], nx = x + d[dir][1]; 
			if(!isValidPos(ny, nx) || office[ny][nx] == 6) break;
			if (office[ny][nx] == 0) {
				office[ny][nx] = WATCHED; 
				ret.emplace_back(ny, nx);
			}
			y = ny, x = nx;
		}
	} 
	else if (office[y][x] == 2) {
		for (int i = 0; i <= 2; i += 2){
			int tny = y, tnx = x;
			while (true){
				int ny = tny + d[(dir + i) % 4][0], nx = tnx + d[(dir + i) % 4][1];
				if (!isValidPos(ny, nx) || office[ny][nx] == 6) break;
				if (office[ny][nx] == 0) {
					office[ny][nx] = WATCHED;
					ret.emplace_back(ny, nx);
				}
				tny = ny, tnx = nx;
			}
		}
	}
    else {
        // office[y][x] - 1번 루프를 돔. (3, 4, 5번 화살표 로직이 똑같아서 합침)
        for (int i = 0; i < office[y][x] - 1; i++) {
			int tny = y, tnx = x;
			while (true){
				int ny = tny + d[(dir + i) % 4][0], nx = tnx + d[(dir + i) % 4][1];
				if (!isValidPos(ny, nx) || office[ny][nx] == 6) break;
				if (office[ny][nx] == 0) {
					office[ny][nx] = WATCHED;
					ret.emplace_back(ny, nx);
				}
				tny = ny, tnx = nx;
			}
		}
    }
	return ret; 
}
void DFS(int idx){
	if (idx == cctv.size()) {
		int cnt = 0;
		for (int y = 0; y < N; ++y)
			for(int x = 0; x < M; ++x)
				if (office[y][x] == 0) cnt++;
		answer = min(answer, cnt);
		return;
	}
	for(int d = 0; d < 4; ++d) {
		vector<pair<int, int>> changedPos = watch(idx, d); 
		DFS(idx + 1);
		for (const auto& pos : changedPos) office[pos.first][pos.second] = 0; 
	}
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	
	cin >> N >> M;
	for(int y = 0; y < N; y++){
		for(int x = 0; x < M; x++){
			cin >> office[y][x];
			if (1 <= office[y][x] && office[y][x] <= 5) cctv.emplace_back(y, x);
		}
	}
	DFS(0);
	cout << answer;
}

소스코드 링크

결과