백준 15683번 감시 C++ 백트래킹, 구현, 시뮬레이션

리뷰

 

모든 CCTV가 바라볼 수 있는 모든 방향을 체크하고 사각지대가 제일 적은 케이스를 찾는 문제

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

 

문제 풀이

1. 전역 변수로는 맵, 방향 배열과 행의 개수 n, 열의 개수 m, cctv의 개수 k, 정답을 출력할 ans를 설정했다.
2. n과 m값을 받아오고 n * m의 맵을 받아온다. 이때 현재 들어온 값이 1이상 이라면 별도의 처리가 필요하다.
3. 입력값이 6인 경우 벽이므로 continue, 1 ~ 5 사이라면 CCTV이므로 cctv 배열에 추가해 준 뒤 k의 개수를 증가시킨다.
4. 이때 각 CCTV의 시야는 모두 다르므로 구조체 CCTV의 look에 각각의 시야각을 추가해 준다.
5. CCTV들의 방향을 저장할 빈 벡터 dirs를 초기화 하고 level 0부터 백트래킹을 시작해 준다.
6. 백트래킹에서는 반복문을 통해 각 CCTV의 초기 방향 각도를 dirs벡터에 추가하고 재귀를 이어나가면 된다.
7. 만약 level이 k 즉, CCTV개수만큼 재귀가 진행되었다면, 현재 수집한 방향을 토대로 시뮬레이션을 돌려준다.
8. 시뮬레이션은 simul 함수에서 진행하며, CCTV들의 초기 방향 정보와 flag를 매개변수로 받는다.
9. flag가 1일 경우 시뮬레이션 시작으로, 각 CCTV에서 볼 수 있는 시야를 모두 -1로 만들어 준다.
10. 시뮬레이션이 완료되었다면 맵에 존재하는 0의 개수를 세어 ans값을 초기화 해준다.
11. 이후 시뮬레이션 돌렸던 내용을 다시 원상복구 시켜주어야 다음 탐색에서도 맵을 활용할 수 있다.
12. flag가 0일 경우 원상복구를 시작하고, 각 CCTV에서 볼 수 있는 시야의 끝까지 갔다가 다시 돌아오면서 -1인 값을 발견하였다면 다시 0으로 만들어 주는 작업을 진행한다.
13. 이후 탐색을 재개해 주고 모든 탐색이 완료되었을 경우 ans에 저장된 답을 출력해 주면 된다.

 

참고 사항

처음엔 dirs변수를 사용하지 않고 바로 시뮬레이션을 돌려볼까 했으나, 원복하는 과정에서 기존의 CCTV와 시야각이 겹칠 경우 모두 지워버리는 경우가 있었다.

따라서 기저조건에 도달 했을때 시뮬레이션을 돌린 후 모두 원복을 시켜준다면 위의 예외는 발생하지 않는다.

물론 매번 모든 CCTV를 돌려주는 것이 중복을 발생시키긴 하지만 주어진 시간 내 실행이 충분히 가능하여 굳이 신경쓰지 않아도 될 것 같다.

 

정답 코드

#include<iostream>
#include<vector>

using namespace std;

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

int n, m, k, ans = 1e9;
int lst[8][8];

struct CCTV {
	int x, y;
	vector<int> look;
};

CCTV cctv[8];

void simul(vector<int>& dirs, int flag) {
	for (int i = 0; i < k; i++) {
		CCTV tv = cctv[i];
		int dir = dirs[i];
		int sx = tv.x, sy = tv.y;
		vector<int>& look = tv.look;
		if (flag) {
			for (int i = 0; i < look.size(); i++) {
				int nd = (dir + look[i]) % 4;
				int nx = sx + dx[nd], ny = sy + dy[nd];
				while (0 <= nx && nx < n && 0 <= ny && ny < m && lst[nx][ny] != 6) {
					if (!lst[nx][ny]) lst[nx][ny] = -1;
					nx += dx[nd];
					ny += dy[nd];
				}
			}
		}
		else {
			for (int i = look.size() - 1; i >= 0; i--) {
				int nd = (dir + look[i]) % 4;
				int nx = sx + dx[nd], ny = sy + dy[nd], ex = sx, ey = sy, flag = 0;
				while (0 <= nx && nx < n && 0 <= ny && ny < m && lst[nx][ny] != 6) {
					ex = nx;
					ey = ny;
					nx += dx[nd];
					ny += dy[nd];
				}
				while (ex != sx || ey != sy) {
					if (lst[ex][ey] == -1) lst[ex][ey] = 0;
					ex -= dx[nd];
					ey -= dy[nd];
				}
			}
		}
	}
}

int chk() {
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (lst[i][j] == 0) cnt++;
		}
	}
	return cnt;
}

void bt(int level, vector<int>& dirs) {
	if (level == k) {
		simul(dirs, 1);
		ans = min(ans, chk());
		simul(dirs, 0);
		return;
	}

	for (int i = 0; i < 4; i++) {
		dirs.push_back(i);
		bt(level + 1, dirs);
		dirs.pop_back();
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> lst[i][j];
			if (0 < lst[i][j]) {
				if (lst[i][j] == 6) continue;
				cctv[k].x = i, cctv[k].y = j;
				if (lst[i][j] == 1) cctv[k].look.push_back(0);
				else if (lst[i][j] == 2) {
					cctv[k].look.push_back(0);
					cctv[k].look.push_back(2);
				}
				else if (lst[i][j] == 3) {
					cctv[k].look.push_back(0);
					cctv[k].look.push_back(1);
				}
				else if (lst[i][j] == 4) {
					cctv[k].look.push_back(0);
					cctv[k].look.push_back(1);
					cctv[k].look.push_back(2);
				}
				else {
					cctv[k].look.push_back(0);
					cctv[k].look.push_back(1);
					cctv[k].look.push_back(2);
					cctv[k].look.push_back(3);
				}
				k++;
			}
		}
	}
	vector<int> dirs;
	bt(0, dirs);
	cout << ans;
}