백준 15683번 - 감시(C++)

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

15683번: 감시

 

삼성 SW 역량 기출 문제 답게 상당한 구현을 요구하는 문제이다.

 

접근법

- 먼저 이 문제는 CCTV들이 4방향이 가능하고 총 5가지 종류가 있다. 모든 CCTV의 상태 별 감시 위치를 확인해야하기 때문에 이 문제는 BRUTEFORCE 완전 탐색 문제이다. 그러나 브루트포스하게 몇 중 반복문으로 해결하기는 힘들다. CCTV의 숫자가 정해져있지 않기 때문이다. 내가 선택한 방법은 DFS 백트래킹 방법이다.

시간복잡도는 4^8 * N * N 이며 N의 최고 차는 8이므로 T.C = 4,194,304이다.

N이 작기 때문에 위 방법이 가능한것이다.

 

먼저 cctvLocate 벡터에 각 CCTV의 위치를 자리시켜두었고 visited[N][4] 를 선언하여 각 CCTV의 번호와 방향을 저장해둘 수 있는 방문체크 배열을 선언하였다.

그리고 

dfs(세팅한 CCTV의 개수){
	if(세팅한 CCTV의 개수 == 총 CCTV 개수)
    	현재 사무실 사각지대 확인()
        return
        
    for(i = 0 ~ 4 각 방향){
    	if(세팅한 방향이면) continue
        visited[CCTV번호][i] = true
        CCTV 세팅()
        dfs(세팅한 CCTV + 1)
        visited[CCTV번호][i] = false 
    }
	
}

 

여기서 중요한 건 CCTV 세팅인데 난 동서남북으로 1자로 쭉 감시하는 함수들을 만들어놓고 각 방향마다 사용했다. 좀 코드가 더럽지만 방법이 떠오르지 않았다.

 

그리고 CCTV를 세팅할 때 가장 중요한 요소가 있는데, 바로 벽은 넘을 수 없지만 CCTV는 통과가 가능하다는 점이다!!

이걸 잘못봐서 넘을 수 없는 줄 알고 30분을 허비했다.

 

문제를 잘 읽자..

 

#include <iostream>
#include <vector>
using namespace std;

vector<pair<int, int>> cctvLocate;

bool visited[9][5] = { false, };
int answer = 456153;
int N, M;
void print(vector<vector<int>> board) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cout << board[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}
int checkCctv(vector<vector<int>> board) {
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (board[i][j] == 0)
				cnt++;
		}
	}

	return cnt;
}

vector<vector<int>> workNorth(vector<vector<int>> board, int x, int y) {
	for (int i = x - 1; i > -1; i--) {
		if (board[i][y] == 6) break;
		else if (board[i][y] == 0) 
			board[i][y] = -1;
	}
	//print(board);
	return board;
}

vector<vector<int>> workSouth(vector<vector<int>> board, int x, int y) {
	for (int i = x + 1; i < N; i++) {
		if (board[i][y] == 6) break;
		else if (board[i][y] == 0)
			board[i][y] = -1;
	}
	return board;
}

vector<vector<int>> workWest(vector<vector<int>> board, int x, int y) {
	for (int i = y - 1; i > -1; i--) {
		if (board[x][i] == 6) break;
		else if (board[x][i] == 0)
			board[x][i] = -1;
	}
	return board;
}

vector<vector<int>> workEast(vector<vector<int>> board, int x, int y) {
	for (int i = y + 1; i < M; i++) {
		if (board[x][i] == 6) break;
		else if (board[x][i] == 0)
			board[x][i] = -1;
	}
	return board;
}



void dfs(int idx, vector<vector<int>> board) {
	if (idx == cctvLocate.size()) {
		//print(board);
		answer = min(answer, checkCctv(board));
		return;
	}
	int x = cctvLocate[idx].first;
	int y = cctvLocate[idx].second;
	
	for (int i = 0; i < 4; i++) {
		if (visited[idx][i] == true) continue;
		visited[idx][i] = true;
		
		vector<vector<int>> work_board;
		work_board = board;

		if (board[x][y] == 1) { // 막대
			if (i == 0) work_board = workNorth(work_board, x, y);
			else if (i == 1) work_board = workEast(work_board, x, y);
			else if (i == 2) work_board = workSouth(work_board, x, y);
			else work_board = workWest(work_board, x, y);
		}
		else if (board[x][y] == 2) { // 양쪽
			if (i == 0) {
				work_board = workNorth(work_board, x, y);
				work_board = workSouth(work_board, x, y);
			}
			else if (i == 1) {
				work_board = workEast(work_board, x, y);
				work_board = workWest(work_board, x, y);
				
			}
			else if (i == 2) {
				work_board = workNorth(work_board, x, y);
				work_board = workSouth(work_board, x, y);
			}
			else {
				work_board = workEast(work_board, x, y);
				work_board = workWest(work_board, x, y);
			}
		}
		else if (board[x][y] == 3) {
			if (i == 0) {
				work_board = workNorth(work_board, x, y);
				work_board = workEast(work_board, x, y);
			}
			else if (i == 1) {
				work_board = workNorth(work_board, x, y);
				work_board = workWest(work_board, x, y);
			}
			else if (i == 2) {
				work_board = workSouth(work_board, x, y);
				work_board = workWest(work_board, x, y);
			}
			else {
				work_board = workSouth(work_board, x, y);
				work_board = workEast(work_board, x, y);
			}
		}
		else if (board[x][y] == 4) {
			if (i == 0) {
				work_board = workNorth(work_board, x, y);
				work_board = workEast(work_board, x, y);
				work_board = workWest(work_board, x, y);
			}
			else if (i == 1) {
				work_board = workSouth(work_board, x, y);
				work_board = workEast(work_board, x, y);
				work_board = workWest(work_board, x, y);
			}
			else if (i == 2) {
				work_board = workNorth(work_board, x, y);
				work_board = workEast(work_board, x, y);
				work_board = workSouth(work_board, x, y);
			}
			else {
				work_board = workNorth(work_board, x, y);
				work_board = workWest(work_board, x, y);
				work_board = workSouth(work_board, x, y);
			}
		}
		else if(board[x][y] == 5) {
			work_board = workNorth(work_board, x, y);
			work_board = workWest(work_board, x, y);
			work_board = workSouth(work_board, x, y);
			work_board = workEast(work_board, x, y);
		}
		dfs(idx + 1, work_board);
		visited[idx][i] = false;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> M;

	vector<vector<int>> space(N, vector<int>(M, 0));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> space[i][j];
			if (space[i][j] != 0 && space[i][j] != 6) cctvLocate.push_back({i, j});
		}
	}

	dfs(0, space);
	cout << answer << '\n';
}