삼성 코딩테스트 기출_(백준)감시

난이도 ★★☆

 

문제출처

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

15683번: 감시

 

포인트

1. 중복조합(백트래킹 재귀함수로 구현)

각각의 CCTV가 네 방향으로 회전할 수 있으며 서로 독립적이다. 따라서 모든 CCTV가 가질 수 있는 모든 방향들의 조합을 설정한 후 map의 상태를 체크해야 한다.

 

2. map 초기화

map의 상태를 체크한 후 다음 상태를 불러오기 이전에 map을 다시 원상복귀하는 작업이 필요하다.

 

3. (시간 관련) CCTV2와 CCTV5는 굳이 네 방향을 모두 돌리지 않아도 된다.

3-1. CCTV2는 상하/좌우 두 경우만 존재

3-2. CCTV5는 상하좌우 한 경우만 존재

따라서 방향 설정을 줄여 줌으로써 시간을 절약할 수 있다.

 

정답코드

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

int N, M;
int map[10][10];

//설치된 CCTV의 개수
int numOfCam;
//최종 정답을 저장할 변수
int ans = 987654321;

struct camera {
	int r;
	int c;
	int type;//1-5 유형
	int dir;//0-3까지 존재하며, 0은 초기상태, 1씩 더해질수록 90도씩 회전한 상태
};

//설치된 CCTV를 저장할 벡터
vector<camera> cctv;

//상-감시
void up(int r, int c) {
	r--;
	while (r >= 0) {
		if (map[r][c] == 6)break;
		if (map[r][c] == 0) {
			map[r][c] = 100;
		}
		r--;
	}
}
//하-감시
void down(int r, int c) {
	r++;
	while (r < N) {
		if (map[r][c] == 6)break;
		if(map[r][c]==0)map[r][c] = 100;
		r++;
	}
}
//좌-감시
void left(int r, int c) {
	c--;
	while (c >= 0) {
		if (map[r][c] == 6)break;
		if(map[r][c]==0)map[r][c] = 100;
		c--;
	}
}
//우-감시
void right(int r, int c) {
	c++;
	while (c < M) {
		if (map[r][c] == 6)break;
		if (map[r][c] == 0)map[r][c] = 100;
		c++;
	}
}

//CCTV작동시키기
int watch(vector<camera> &cctv) {
    //사각지대 개수를 저장할 변수
	int nonWatched = 0;
    
    //전체 CCTV를 모두 순회
	for (int i = 0; i < cctv.size(); i++) {
        //현재 CCTV를 임시 저장
		camera cur = cctv[i];
        //1-5유형별로 구분
		switch (cur.type) {
		case 1:
			if (cur.dir == 0) {//초기상태
				right(cur.r, cur.c);
			}
			else if (cur.dir == 1) {//90도 회전
				down(cur.r, cur.c);
			}
			else if (cur.dir == 2) {//180도 회전
				left(cur.r, cur.c);
			}
			else {//270도 회전
				up(cur.r, cur.c);
			}
			break;
		case 2:
			if (cur.dir == 0 || cur.dir == 2) {
				left(cur.r, cur.c);
				right(cur.r, cur.c);
			}
			else {
				up(cur.r, cur.c);
				down(cur.r, cur.c);
			}
			break;
		case 3:
			if (cur.dir == 0) {
				up(cur.r, cur.c);
				right(cur.r, cur.c);
			}
			else if (cur.dir == 1) {
				right(cur.r, cur.c);
				down(cur.r, cur.c);
			}
			else if (cur.dir == 2) {
				down(cur.r, cur.c);
				left(cur.r, cur.c);
			}
			else {
				left(cur.r, cur.c);
				up(cur.r, cur.c);
			}
			break;
		case 4:
			if (cur.dir == 0) {
				left(cur.r, cur.c);
				up(cur.r, cur.c);
				right(cur.r, cur.c);
			}
			else if (cur.dir == 1) {
				up(cur.r, cur.c);
				right(cur.r, cur.c);
				down(cur.r, cur.c);
			}
			else if (cur.dir == 2) {
				right(cur.r, cur.c);
				down(cur.r, cur.c);
				left(cur.r, cur.c);
			}
			else {
				down(cur.r, cur.c);
				left(cur.r, cur.c);
				up(cur.r, cur.c);
			}
			break;
		case 5:
			up(cur.r, cur.c);
			down(cur.r, cur.c);
			left(cur.r, cur.c);
			right(cur.r, cur.c);
			break;
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 0)nonWatched++;
		}
	}
    //사각지대의 개수 반환
	return nonWatched;
}

//map 초기화
void initialize() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 100)map[i][j] = 0;
		}
	}
}

//방향설정
void setDir(int idx, vector<camera> &cctv) {
    //모든 카메라에 대한 방향설정이 끝난 경우
	if (idx == numOfCam) {
        //카메라 작동시켜서 사각지대 개수 구하기
		int cnt = watch(cctv);
        //최솟값 업데이트하기
		if (cnt < ans)ans = cnt;
        //map 초기화
		initialize();
		return;
	}

    //2번 CCTV는 두 방향만 있음
    if(cctv[idx].type==2){
        for(int i=0;i<2;i++){
            cctv[idx].dir=i;
            setDir(idx+1,cctv);
        }
    }
    //5번 CCTV는 한 방향만 있음
    else if(cctv[idx].type==5){
        cctv[idx].dir=1;
        setDir(idx+1,cctv);
    }
    //다른 모든 CCTV는 네 방향 다 고려
    else{
	    for (int i = 0; i < 4; i++) {
		    cctv[idx].dir = i;
		    setDir(idx + 1, cctv);
	    }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
			if (map[i][j] >= 1 && map[i][j] <= 5) {
				cctv.push_back({ i,j,map[i][j],0 });
			}
		}
	}

	numOfCam = cctv.size();

	setDir(0, cctv);

	cout << ans << endl;

	return 0;
}