백준_삼성 sw역량 기출 문제_15683_감시

[youbeen2798]

문제 링크 : https://www.acmicpc.net/problem/15683
문제 난이도 : 골4 ( 개인적으로 다른 골4보다 어려운 것 같음..)
문제 알고리즘 : 시뮬레이션

문제 내용

• 1번 카메라는 한쪽 방향을 감시
• 2번 카메라는 동, 서 // 남, 북 처럼 서로 다른 방향을 감시
• 3번 카메라는 90도 차이로 감시(ex. 동, 북 // 서, 남...)
• 4번 카메라는 세 방향 감시
• 5번 카메라는 전체 방향 감시
• 문제에는 빈방, 카메라, 벽이 있으며 카메라는 벽을 통과할 수 없음
• 카메라의 방향을 적절히 정해서 사각지대(카메라가 볼 수 없는 위치)의 최소값을 구하는 문제

풀이 방법

• 시뮬레이션으로, 일일이 카메라의 방향을 다 돌려보며 구한다
• 즉, 모든 카메라에 대해 감시 공간을 설정 후 감시 되지 않은 공간을 계산
• 따라서, 각 카메라가 감시하는 공간을 체크할 함수(update)와, 모든 카메라를 하나씩 차례대로 검색하는 함수(solve)를 만듦
• for문을 이용하여 각 카메라의 모든 방향을 탐색하는 것 ( 백트래킹 ) 과 backup이라는 아이디어가 이 문제의 핵심!

풀이 코드

#include <iostream>

using namespace std;

int row;
int col;
int CAM_SIZE = 0;
int office[8][8];

int answer = 100;

struct CAM {
	int x, y, type;
};

CAM cam[8];

int rotation[5] = { 4,2,4,4,1 }; //카메라 타입에 맞는 감시 방법 개수

void update(int dir, CAM c) {

	dir %= 4;

	if (dir == 0) { //오른쪽
		for (int y = c.y + 1; y < col; y++) {
			if (office[c.x][y] == 6) {
				break;
			}
			office[c.x][y] = -1;
		}
	}
	else if (dir == 1) { //위쪽
		for (int x = c.x - 1; x >= 0; x--) {
			if (office[x][c.y] == 6) {
				break;
			}
			office[x][c.y] = -1;
		}
	}
	else if (dir == 2) { //왼쪽
		for (int y = c.y - 1; y >= 0; y--) {
			if (office[c.x][y] == 6) {
				break;
			}
			office[c.x][y] = -1;
		}
	}
	else if (dir == 3) { //아래쪽
		for (int x = c.x + 1; x < row; x++) {
			if (office[x][c.y] == 6) {
				break;
			}
			office[x][c.y] = -1;
		}
	}
}

void copy(int backup[8][8], int origin[8][8]) {
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			backup[i][j] = origin[i][j];
		}
	}
}

void solve(int cam_idx) { //카메라 차례대로 검색(백트래킹)
	
	if (cam_idx == CAM_SIZE) {

		int w = 0;
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				if (office[i][j] == 0) { //빈 방개수 일일이 체크
					w++;
				}
			}
		}

		if (answer > w) { //빈 방개수가 최소값 갱신
			answer = w;
		}
		return;
	}
	int type = cam[cam_idx].type; //카메라 타입
	int backup[8][8];

	//모든 방향을 하나하나 탐색
	for (int dir = 0; dir < rotation[type]; dir++) {

		//나중에 office를 직접 탐색 후, 다시 백업하기 위함
		copy(backup, office);

		
		if (type == 0) {
			update(dir, cam[cam_idx]);
		}
		else if (type == 1) {
			update(dir, cam[cam_idx]);
			update(dir + 2, cam[cam_idx]);
		}
		else if (type == 2) {
			update(dir, cam[cam_idx]);
			update(dir + 1, cam[cam_idx]);
		}
		else if (type == 3) {
			update(dir, cam[cam_idx]);
			update(dir +1, cam[cam_idx]);
			update(dir +2, cam[cam_idx]);
		}
		else if (type == 4) {
			update(dir, cam[cam_idx]);
			update(dir + 1, cam[cam_idx]);
			update(dir + 2, cam[cam_idx]);
			update(dir + 3, cam[cam_idx]);
		}

		solve(cam_idx + 1);
		copy(office, backup); // 전 dir로 돌아가기 위해 백업
	}
}
int main() {
	ios_base::sync_with_stdio(0); //입출력 빠르게
	cin.tie(0);
	cout.tie(0);

	cin >> row >> col; //세로크기(행) >> 가로크기(열)

	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			cin >> office[i][j];

			if (office[i][j] != 0 && office[i][j] != 6) { // 카메라가 있다면
				cam[CAM_SIZE].x = i; //카메라 위치 좌표
				cam[CAM_SIZE].y = j; //카메라 위치 좌표
				cam[CAM_SIZE].type = office[i][j] - 1; // 카메라 타입( 1이면 0, 2면 1, 3이면 2, 4면 3, 5면 4)

				CAM_SIZE++; //카메라 개수
			}

		}
	}

	solve(0);

	cout << answer;
}