문제

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

---

풀이

참고: https://yabmoons.tistory.com/46

이 문제는 cctv가 특정 방향으로 감시할 때 사각지대 크기의 최솟값을 구해야 하므로, 모든 경우의 수를 따져야 하는 완전탐색 문제이다.

1. 먼저 그래프 정보를 입력 받을 때, cctv에 관한 정보를 {{x, y}, {번호, 방향}} 이렇게 묶어서 벡터에 저장한다. (방향은 -1로 초기화)
2. 이후 모든 cctv의 감시 방향을 설정해준다. 예를 들어, 그래프에 존재하는 cctv가 1번, 2번 하나씩 있다고 할 때, 1번은 동/서/남/북 중에 한 방향으로만 감시 가능하고, 2번은 동서/남북 이렇게 두 방향으로 감시 가능하다. 그렇다면, (1번: 동, 2번: 동서), (1번: 동, 2번: 남북) 등등 모든 경우의 수를 고려해야 한다.
3. 2번에서 말한 방향을 설정해주기 위해서 setDirection 함수를 이용한다. cctv 방향을 0, 1, 2, 3 (동서남북) 으로 바꿔가면서 사각지대 영역 크기를 계산하고 그 중에서 최솟값을 구하면 된다.

void setDirection(int idx) {
	if(idx == cctvCount) {
    	checkVisibleArea(); 
        ans = min(ans, getUnvisibleAreaSize()); 
    }
    
    cctv[idx].second.second = 0;
    setDirection(idx + 1); 
    
    cctv[idx].second.second = 1;
    setDirection(idx + 1);
    
    cctv[idx].second.second = 2;
    setDirection(idx + 1); 
    
    cctv[idx].second.second = 3;
    setDirection(idx + 1); 
}

위의 함수에서 재귀가 호출되는 과정을 생각해보자.

예를 들어, cctv가 3개이고 종류는 1, 3, 5번이라고 하자. 그러면 아래와 같이 재귀적으로 함수가 호출되다가

idx: 0, cctv[0].second.second = 0
idx: 1, cctv[1].second.second = 0
idx: 2, cctv[2].second.second = 0

idx == 3일 때 조건문에 걸려서 계산 과정에 들어간다.

이후 함수가 리턴되면서 바로 이전에 함수가 호출된 그 시점으로 돌아간다. (스택의 pop)

즉, cctv[2].second.second = 1 이 부분이 실행된다.

그러면 이제까지 구한 경우의 수는 다음과 같을 것이다.

(1번: 동, 3번: 동, 5번: 동), (1번: 동, 3번: 동, 5번: 서)

이런 식으로 모든 cctv에 대한 방향을 설정하고, 그 경우의 수 중에서 사각지대의 최솟값을 구하면 된다.

그리고 cctv 방향에 따라 감시 가능한 영역을 체크할 때 -1로 표시할 건데, 이는 원본 배열이 아니라 복사본 배열에 표시해야 한다. 다음 경우의 수를 위해 원본 배열의 상태는 계속 동일하게 유지되어야 하기 때문이다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int, int> pii;

const int MAX = 9;
int N, M;

int graph[MAX][MAX]; 
int temp[MAX][MAX]; 
vector<pair<pii, pii>> cctv;

int ans = 1e9;
int cctvCount = 0;

// 동서남북 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void input() {
	cin >> N >> M;

	// 0: 빈칸, 6: 벽, 1~5: CCTV
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			cin >> graph[i][j];
			
			if(graph[i][j] >= 1 && graph[i][j] <= 5){
				// {{x, y}, {번호, 방향}}
				cctv.push_back({{i, j}, {graph[i][j], -1}});
			}
		}
	}

	// cctv 총 개수 초기화 
	cctvCount = cctv.size();
}

void copyGraphArray() {
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			temp[i][j] = graph[i][j]; 
		}
	}
}

void moveRight(int x, int y){
	for(int i = y + 1; i < M; i++){
		if(temp[x][i] == 6) break; 
		if(temp[x][i] >= 1 && temp[x][i] <= 5) continue; 
		temp[x][i] = -1; 
	}
}

void moveLeft(int x, int y){
	for(int i = y - 1; i >= 0; i--){
		if(temp[x][i] == 6) break; 
		if(temp[x][i] >= 1 && temp[x][i] <= 5) continue; 
		temp[x][i] = -1; 
	}
}

void moveBottom(int x, int y){
	for(int i = x + 1; i < N; i++){
		if(temp[i][y] == 6) break; 
		if(temp[i][y] >= 1 && temp[i][y] <= 5) continue; 
		temp[i][y] = -1; 
	}
}

void moveTop(int x, int y){
	for(int i = x - 1; i >= 0; i--){
		if(temp[i][y] == 6) break; 
		if(temp[i][y] >= 1 && temp[i][y] <= 5) continue; 
		temp[i][y] = -1; 
	}
}

void checkVisibleArea() {
	copyGraphArray(); 

	for(int i = 0; i < cctv.size(); i++){
		int x = cctv[i].first.first;
		int y = cctv[i].first.second; 
		int num = cctv[i].second.first;
		int dir = cctv[i].second.second; 

		// 동서남북 중에 한 방향 
		if(num == 1){
			if(dir == 0){
				moveRight(x, y);
			}else if(dir == 1){
				moveLeft(x, y);
			}else if(dir == 2){
				moveBottom(x, y);
			}else if(dir == 3){
				moveTop(x, y);
			}
		}
		// 동서 또는 남북 중에 한 방향 
		else if(num == 2){
			if(dir == 0 || dir == 1){
				moveRight(x, y);
				moveLeft(x, y);
			}else if(dir == 2 || dir == 3){
				moveBottom(x, y);
				moveTop(x, y);
			}
		}
		// 90도 방향 
		else if(num == 3){
			if(dir == 0){
				moveRight(x, y);
				moveTop(x, y);
			}else if(dir == 1){
				moveLeft(x, y);
				moveBottom(x, y);
			}else if(dir == 2){
				moveRight(x, y);
				moveBottom(x, y);
			}else if(dir == 3){
				moveLeft(x, y);
				moveTop(x, y);
			}
		}
		// 세 방향
		else if(num == 4){
			if(dir == 0){
				moveRight(x, y);
				moveTop(x, y);
				moveBottom(x, y);
			}else if(dir == 1){
				moveLeft(x, y);
				moveTop(x, y);
				moveBottom(x, y);
			}else if(dir == 2){
				moveRight(x, y);
				moveLeft(x, y);
				moveBottom(x, y);
			}else if(dir == 3){
				moveRight(x, y);
				moveLeft(x, y);
				moveTop(x, y);
			}
		}
		// 동서남북 모든 방향 
		else if(num == 5){
			moveRight(x, y);
			moveLeft(x, y);
			moveBottom(x, y);
			moveTop(x, y);
		}
	}
}

int getUnvisibleAreaSize() {
	int cnt = 0;
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			if(temp[i][j] == 0) cnt++; 
		}
	}
	return cnt;
}

void setDirection(int idx) {
	if(idx == cctvCount){
		checkVisibleArea(); 
		ans = min(ans, getUnvisibleAreaSize());
		return;
	}

	cctv[idx].second.second = 0; 
	setDirection(idx + 1);

	cctv[idx].second.second = 1; 
	setDirection(idx + 1);

	cctv[idx].second.second = 2; 
	setDirection(idx + 1);

	cctv[idx].second.second = 3; 
	setDirection(idx + 1);
}

int main()
{	
	ios::sync_with_stdio(0);
	cin.tie(0);

	input();

	setDirection(0); 

	cout << ans; 

	return 0; 
}