백준 15683_감시

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

15683번: 감시

해당 문제는 DFS로 해결했다.

CCTV들의 위치를 기록해두고 해당 CCTV들의 방향을 하나씩 조정해가며 모든 CCTV의 방향을 조정하였을 때 CCTV 방향별로 빈칸을 지워나가는 함수를 구현하였다.

 

지워나가는 함수에서 고려해야할 것은 CCTV가 타입별로 커버할 수 있는 방향이다.

여기서 지정방향은 동쪽을 기준으로 시작된다.

(0 북 1 동 2 서 3 남)

1번은 무조건 지정방향

2번은 지정방향 + (지정반대 + 2)%4 방향

3번은 지정방향 + (지정방향 + 3)%4 방향

4번은 지정방향 + (지정반대 + 2)%4 방향 + (지정방향 + 3)%4 방향

5번은 지정방향 + (지정반대 + 2)%4 방향 + (지정방향 + 3)%4 방향 + (지정방향 +1)%4 방향 

 

그리고 해당방향으로 빈칸을 다 지워나간 후의 '남은 빈 칸의 수'를 계산하는 방식으로 실행했다.

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

int mp[8][8]; // 사무실
vector<pair<int,int>> cc; // CCTV 위치
vector<int> dir; // CCTV 방향
int dx[4] = { -1,0,1,0 }; // 북 동 남 서
int dy[4] = { 0,1,0,-1 }; // 북 동 남 서
int ans = 0;

// 공간 체크
void space_check(int n, int m) {
	// copy 
	int cnt = 0;
	int mpc[8][8];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			mpc[i][j] = mp[i][j];

	// cctv 탐색하기
	for (int i = 0; i < cc.size(); i++) {
		int x = cc[i].first, y = cc[i].second; // x,y
		int d = dir[i]; // 방향 dir
		int t = mp[x][y]; // cctv type

		// CASE 1.
		// 범위를 넘어가면 중단
		int nx = x + dx[d], ny = y + dy[d]; // 다음 공간
		while (nx >= 0 && nx<n && ny >= 0 && ny < m && mpc[nx][ny] != 6) {
			if (mpc[nx][ny] == 0)
				mpc[nx][ny] = -1;
			nx = nx + dx[d], ny = ny + dy[d]; // 다음 공간
		}

		// CASE 2(반대방향 2,4,5)
		// 범위를 넘어가면 중단
		if (t == 2 || t == 4 || t == 5) {
			int nd = (d + 2) % 4;
			int nx = x + dx[nd], ny = y + dy[nd]; // 다음 공간
			while (nx >= 0 && nx<n && ny >= 0 && ny < m && mpc[nx][ny] != 6) {
				if (mpc[nx][ny] == 0)
					mpc[nx][ny] = -1;
				nx = nx + dx[nd], ny = ny + dy[nd]; // 다음 공간
			}
		}
		// CASE 2(시계회전방향 5)
		// 범위를 넘어가면 중단
		if (t == 5) {
			int nd = (d + 1) % 4;
			int nx = x + dx[nd], ny = y + dy[nd]; // 다음 공간
			while (nx >= 0 && nx<n && ny >= 0 && ny < m && mpc[nx][ny] != 6) {
				if (mpc[nx][ny] == 0)
					mpc[nx][ny] = -1;
				nx = nx + dx[nd], ny = ny + dy[nd]; // 다음 공간
			}
		}

		// CASE 3(반시계회전방향 3,4,5)
		// 범위를 넘어가면 중단
		if (t == 3 || t == 4 || t == 5) {
			int nd = (d + 3) % 4;
			int nx = x + dx[nd], ny = y + dy[nd]; // 다음 공간
			while (nx>=0 && nx<n && ny >= 0 && ny < m && mpc[nx][ny] != 6) {
				if (mpc[nx][ny] == 0)
					mpc[nx][ny] = -1;
				nx = nx + dx[nd], ny = ny + dy[nd]; // 다음 공간
			}
		}
	}
	// 탐색
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (mpc[i][j] == 0)
				cnt++;
		}
	}

	// 최소값 비교
	if (ans > cnt) {
		ans = cnt;
	}
}

// dfs
void dfs(int idx, int n, int m) {
	// all visit
	if (idx == cc.size()) {
		// 비교 함수
		space_check(n, m);
		return;
	}
	
	// x, y
	int x = cc[idx].first, y = cc[idx].second;
	int cctv = mp[x][y]; // 몇 번 cctv 인가
	
	// 1번~4번 일 경우
	if (cctv >= 1 && cctv <= 4) {
		for (int i = 0; i < 4; i++) {
			dir[idx] = (dir[idx] + 1) % 4; // 시계회전
			dfs(idx + 1, n, m); // recursive
		}
	}

	// 5번 일 경우(회전해도 감시하는 공간 똑같으므로)
	else if (cctv == 5) {
		dfs(idx + 1, n, m);
	}
}

int main() {
	int n, m;
	cin >> n >> m;

	// input
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			cin >> mp[i][j];
			// CCTV
			if (mp[i][j] != 0 && mp[i][j] != 6) {
				pair<int, int> tmp(i, j);
				cc.push_back(tmp);
				dir.push_back(1);
			}
			if (mp[i][j] == 0)
				ans++;
		}

	// solution
	dfs(0, n, m);
	cout << ans;
}