[백준] 감시

감시

이 문제는 복기된 삼성 기출 문제입니다.

이 문제는 다음과 같이 바라볼 수 있는 CCTV를 어떻게 배치해야지만 사각지대를 줄이고 많은 곳을 볼 수 있는지를 출력하는 문제입니다.

전체 맵 최대 크기가 8*8이라 복잡한 알고리즘보단 완전탐색으로 구현이 가능한 문제입니다.

우선 저는 가장먼저 저렇게 바라보는 방향이 다른 cctv를 어떻게 구현할까였습니다. 각 cctv가 가지고있는 정보를 strict로 구현해서 입력받을 때 저장한 뒤, 방향을 나타내는 배열을 dx,dy로 구현해두고 각각 up right down left로 이동하도록 표현한 다음에 그 방향을 가리키는 bool변수가 true면 그 방향으로 가능한 모든 길을 찾는 방향으로 구현을 시작하였습니다.

move_fill() 함수를 보면 cctv종류에 따라서 bool 값을 설정해뒀습니다.

그 이후 모든 cctv가 바라보는 방향을 설정해서 갯수를 세야하기 때문에 dfs개념이 포함된 rotate_cctv 함수를 구현했습니다.

모든 cctv가 방향이 결정되면 방향에 맞게 카피된 맵의 관찰 가능한 좌표를 업데이트를 하고(cctv_watch와 watch_spot 함수) 0의 갯수를 센 다음 최소값을 구하는 방향으로 진행하였습니다.

제가 설명을 잘 못해서 이해가 안갈 수 있으니… 궁금한 점 있으시면 댓글 달아주시면 감사하겠습니다 ㅠㅠ

풀이는 다음과 같습니다.

Source Code:

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

int N, M, answer = numeric_limits<int>::max();
int office[8][8];
int office_copy[8][8];

struct info {
	int x, y, cctv, dir; // cctv 위치와 cctv종류 cctv 방향을 결정 
};
// cctv 는 1,2,3,4,5 이렇게 들어감 

vector<info> CCTV;
vector<vector<bool>> cctv_move[6][4];

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

void move_fill() {

	for (int i = 0; i < 4; i++) {
		vector<bool> tmp(4, false);
		tmp[i] = true;
		cctv_move[1][i].push_back(tmp);
		tmp[i] = false;
	}
	for (int i = 0; i < 4; i++) {
		vector<bool> tmp(4, false);
		tmp[i] = true;
		tmp[(i + 2) % 4] = true;
		cctv_move[2][i].push_back(tmp);
		tmp[i] = false;
		tmp[(i + 2) % 4] = false;
	}
	for (int i = 0; i < 4; i++) { // ㅣ ㅡ
		vector<bool> tmp(4, false);
		tmp[i] = true;
		tmp[(i + 1) % 4] = true;
		cctv_move[3][i].push_back(tmp);
		tmp[i] = false;
		tmp[(i + 1) % 4] = false;
	}
	for (int i = 0; i < 4; i++) { // ㅏ ㅜ ㅓ ㅗ
		vector<bool> tmp(4, false);
		tmp[i] = true;
		tmp[(i + 1) % 4] = true;
		tmp[(i + 2) % 4] = true;
		cctv_move[4][i].push_back(tmp);
		tmp[i] = false;
		tmp[(i + 1) % 4] = false;
		tmp[(i + 2) % 4] = false;
	}
	vector<bool> tmp(4, true);
	for (int i = 0; i < 4; i++) { // +
		cctv_move[5][i].push_back(tmp);
	}
}

void copy() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			office_copy[i][j] = office[i][j];
		}
	}
}

void watch_spot(int cx,int cy,int d) { // cctv가 볼수 있는 좌표 업데이트
	int x = cx;
	int y = cy;
	while (1) {
		int nx = x + dx[d];
		int ny = y + dy[d];

		if (nx < 0 || nx >= N || ny < 0 || ny >= M)break;
		if (office_copy[nx][ny] == 6) break;
		if (office_copy[nx][ny] != 0) { // 0이 아니라면 cctv거나 이미 관찰 가능한 곳이거나 
			x = nx;
			y = ny;
		}
		else {
			office_copy[nx][ny] = 7;
			x = nx;
			y = ny;
		}
	}
}

void cctv_watch() { // 방향이 결정된 모든 cctv가 볼수있는 좌표 확인 
	copy();
	for (auto cc : CCTV) {
		int x = cc.x;
		int y = cc.y;
		int cctv = cc.cctv; // cctv 종류
		int dir = cc.dir; // 방향 

		for (int i = 0; i < 4; i++) {
			if (cctv_move[cctv][dir][0][i]) {
				watch_spot(x, y, i);
			}
		}
	}
}

int cctv_watch_count() { // 못보는 사각지대 갯수 세기
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (office_copy[i][j] == 0)
				cnt++;
		}
	}
	return cnt;
}

void rotate_cctv(int cnt) { // cctv 방향 설정 
	if (cnt == CCTV.size()) {
		cctv_watch();
		int blind_spot = cctv_watch_count();
		answer = min(answer, blind_spot);
		return;
	}

	CCTV[cnt].dir = 0;
	rotate_cctv(cnt + 1);
	CCTV[cnt].dir = 1;
	rotate_cctv(cnt + 1);
	CCTV[cnt].dir = 2;
	rotate_cctv(cnt + 1);
	CCTV[cnt].dir = 3;
	rotate_cctv(cnt + 1);
}

int main() {
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> office[i][j];
			if (office[i][j] != 0 && office[i][j] != 6) {
				CCTV.push_back({ i,j,office[i][j],-1 }); // 처음엔 방향 안정해줌 
			}
		}
	}

	move_fill();


	rotate_cctv(0);

	cout << answer;

	return 0;
}

궁금하신 점은 댓글 남겨 주세요!!

Summary

• 조심으로 돌아가고 있습니다.