[백준 15683][C++] 감시

문제

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

15683번: 감시

[참고 링크 : 주성호 님의 글]

 

풀이 과정

1. 각 카메라의 타입별로 동작에 맞는 감시 함수가 필요하다.

    이를 위해 한 방향을 감시하는 함수를 작성하여 타입에 맞게 적용한다.

    각 카메라의 타입마다 가능한 경우의 수가 정해져 있다. (타입별 4, 2, 4, 4, 1 가지의 경우 가능)

2. 모든 경우를 탐색하기 위해 DFS를 이용했다.

    DFS를 통해 카메라를 하나씩 방문하여 모든 카메라를 방문할 때까지 방문한다.

    모든 카메라를 방문했다면 그 상태의 사각지대를 구하여 ans 값에 업데이트한다.

3. 모든 경우 탐색 후 ans 값을 출력한다.

 

 

세부 풀이

(1)

한 방향을 감시하는 watch 함수를 작성했다. 이 함수는 인자로 d, x, y, 값을 받는다. x, y를 기준으로 인자 d 값을 이용해 감시 방향을 설정하여 탐색 및 변환을 진행한다. 만약 다음 칸이 벽이라면 탐색을 종료하고, 다음 칸이 공백이라면 -1로 변환하여 감시 영역임을 저장했다.

여기서 watch 함수의 switch 문의 순서가 중요하다. 일정한 방향으로 설정해야 한다. 필자는 위쪽을 시작점으로 시계방향의 순서로 구현하였다. 왜냐하면 이후 타입별 적용 시 나머지 연산을 통해 순환하는 구조를 이용할 것이기 때문이다.

 

(2)

문제의 입력을 받을 때, 각 cctv의 정보(type, x, y) 값을 vector에 저장하여 해당 vector를 DFS로 탐색하는 방식으로 구현되었다.

 

watch 함수를 이용하여 각 카메라 타입별 감시하는 상황을 DFS 내부에 표현했다. (Line 109 - 133)

각 타입에 대한 모든 경우의 수는 아래와 같다.

    1번 타입 : (위) 경우를 시계방향으로 한 바퀴 회전시켜 얻을 수 있는 4가지 경우

    2번 타입 : (위/아래) 경우를 시계방향으로 회전시켜 얻을 수 있는 2가지 경우

    3번 타입 : 직각을 이루는 형태인 (위/오른쪽) 경우를 시계방향으로 회전시켜 얻을 수 있는 4가지 경우

    4번 타입 : 한쪽 방향을 제외한 나머지 방향을 포함하는 경우를 시계방향으로 회전시켜 얻을 수 있는 4가지 경우

    5번 타입 : 모든 방향을 포함하는 1가지 경우

한 방향 / 서로 반대인 두 방향 / 연속된 두 방향 / 연속된 세 방향 / 연속된 네 방향에 대한 감시를 적용한다.

 

Line 97의 cam_settings_num을 보면 {0, 4, 2, 4, 4, 1} 이 저장되어 있다. 이는 배열에 타입별 최대 경우의 수를 저장해놓은 배열이다.

이 배열을 이용하여 Line 116에서 for문을 통해 타입별 경우의 수만큼만 반복을 진행하도록 구현했다.

 

한 cctv에 대한 경우를 설정한 뒤 다음 cctv를 DFS를 이용해 탐색하고 돌아왔다면 이전의 map으로 복원하는 과정을 거친다.

최종적으로 마지막 cctv에 대한 설정을 마쳤다면, 그 상황에서의 사각지대 수를 ans와 비교하여 작은 값을 ans에 업데이트한다.

 

(3)

DFS알고리즘에 의해 입력된 cctv들의 모든 경우에 해당하는 상황을 탐색했을 때, 최소 사각지대의 수가 ans에 저장되어 있을 것이다. 해당 ans를 출력한다.

 

소스 코드

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#define m_max 8
using namespace std;

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

int N,M;
int map[m_max][m_max];
vector<cctv> cam_vector;
int ans = -1;


void Input(){
	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]!=0 && map[i][j]!=6){
				cam_vector.push_back({map[i][j],i,j});
			}
		}
	}
}


void watch(int d, int x, int y){
	//dfs 를 진행할 때 방향 조정을 위해 나머지 연산
	d %= 4;
	switch (d) {
		//위
		case 0:
			for(int i=x-1; i>=0; i--){
				if(map[i][y] == 6){
					break;
				}
				else if(map[i][y] == 0){
					map[i][y] = -1;
				}
			}
			break;
		//오른쪽
		case 1:
			for(int i=y+1; i<M; i++){
				if(map[x][i] == 6){
					break;
				}
				else if(map[x][i] == 0){
					map[x][i] = -1;
				}
			}
			break;
		//아래
		case 2:
			for(int i=x+1; i<N; i++){
				if(map[i][y] == 6){
					break;
				}
				else if(map[i][y] == 0){
					map[i][y] = -1;
				}
			}
			break;

		//왼쪽 (case 3)
		default:
			for(int i=y-1; i>=0; i--){
				if(map[x][i] == 6){
					break;
				}
				else if(map[x][i] == 0){
					map[x][i] = -1;
				}
			}
			break;
	}
}


//DFS 를 통해 각 cam 하나씩 접근한다.
//Input에서 저장한 cam_vector를 이용한다.
int cam_settings_num[6] = {0, 4, 2, 4, 4, 1};
void DFS(int idx_cam){
	if(idx_cam==cam_vector.size()){
		int bs=0;
		for(int i=0;i<N;i++){
			for(int j=0;j<M;j++){
				if(map[i][j]==0) bs++;
			}
		}
		if(ans == -1) ans = bs;
		else ans = min(bs, ans);
		return;
	}

	int copy_map[m_max][m_max];

	int type = cam_vector[idx_cam].type;
	int x = cam_vector[idx_cam].x;
	int y = cam_vector[idx_cam].y;
	for(int i=0;i<cam_settings_num[type];i++){
		//이전 상태 저장
		memcpy(copy_map, map, sizeof(int)*m_max*m_max);
		
		switch (type) {
			//각 캠 종류마다 다른 감시 시행
			case 1:
				watch(i,x,y);
				break;
			case 2:
				watch(i,x,y);
				watch(i+2,x,y);
				break;
			case 3:
				watch(i,x,y);
				watch(i+1,x,y);
				break;
			case 4:
				watch(i,x,y);
				watch(i+1,x,y);
				watch(i+2,x,y);
				break;
			default:
				watch(i,x,y);
				watch(i+1,x,y);
				watch(i+2,x,y);
				watch(i+3,x,y);
				break;
		}
		DFS(idx_cam+1);
		//원래 상태로 복원
		memcpy(map, copy_map, sizeof(int)*m_max*m_max);
	}
}

int main(){
	Input();
	DFS(0);
	cout << ans;
	return 0;
}

 

결과 및 후기

저번 겨울 방학 시기 때 코딩 테스트를 준비하면서 틀렸습니다로 끝났던 문제를 발견하여 다시 풀어보았다. 하지만 그때처럼 스스로 설정한 제한 시간 내에 풀지 못하여 풀이를 찾아보고 문제를 마무리하였다. 하나의 함수를 모든 경우에 재활용할  수 있는 아이디어가 굉장히 좋아서 해당 코드를 참고하여 풀이를 진행했다. 코드 길이와 동작 원리의 이해가 훨씬 깔끔했다.