[백준 15683] 감시

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

15683번: 감시

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
int N, M;
int board[8 + 2][8 + 2];
int blank;
int ans;

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

std::vector<_st> V;

int choice[8 + 2];	// cctv 최대 개수 8개


struct _qt
{
	int x, y;
};
std::queue<_qt> Q;
int visited[8 + 2][8 + 2];


// lookup table
// 고른 방향, 해당 방향에 대한 감시카메라 작동 방향 
int CCTV1[4] = { 0, 1, 2, 3 };
int CCTV2[4][2] = {
	{0, 2}, {1, 3}, {2, 0}, {3, 1}
};
int CCTV3[4][2] = {
	{0, 1}, {1, 2}, {2, 3}, {3, 0}
};
int CCTV4[4][3] = {
	{0, 1, 3}, {0, 1, 2}, {1, 2, 3}, {0, 2, 3}
};
int CCTV5[4][4] = {
	{0, 1, 2, 3}, {0, 1, 2, 3}, {0, 1, 2, 3}, {0, 1, 2, 3}
};




void input()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &board[i][j]);
			if (board[i][j] >= 1 && board[i][j] <= 5) V.push_back({ board[i][j], i, j });
			if (board[i][j] == 0) blank++;
		}
	}
	ans = blank;
}



void chk(int idx, int p)
{
	// dir
	int dir_x[4] = { -1, 0, 1, 0 };
	int dir_y[4] = { 0, 1, 0, -1 };

	// init
	Q = {};
	Q.push({ V[idx].x, V[idx].y });
	visited[V[idx].x][V[idx].y] = 1;

	while (!Q.empty()) {
		_qt data = Q.front();
		Q.pop();

		int nx = data.x + dir_x[p];
		int ny = data.y + dir_y[p];

		if (nx < 0 || nx > N - 1 || ny < 0 || ny > M - 1) continue;
		if (board[nx][ny] == 6) continue;
		// 어차피 한 방향으로만 이동하므로 갔던 방향에서 되돌아올 일 없음 
		// visited 체크할 필요 없음 
		Q.push({ nx, ny });
		visited[nx][ny] = 1;
	}
}



void watch_CCTV(int idx, int type, int dir)
{
	switch (type)
	{
	case 1:
		chk(idx, CCTV1[dir]);
		break;
	case 2:
		chk(idx, CCTV2[dir][0]);
		chk(idx, CCTV2[dir][1]);
		break;
	case 3:
		chk(idx, CCTV3[dir][0]);
		chk(idx, CCTV3[dir][1]);
		break;
	case 4: 
		chk(idx, CCTV4[dir][0]);
		chk(idx, CCTV4[dir][1]);
		chk(idx, CCTV4[dir][2]);
		break;
	case 5:
		chk(idx, CCTV5[dir][0]);
		chk(idx, CCTV5[dir][1]);
		chk(idx, CCTV5[dir][2]);
		chk(idx, CCTV5[dir][3]);
		break;
	}
}


int cant_see_area()
{
	int cnt = 0;
	for (int i = 0; i < N; i++) { 
		for (int j = 0; j < M; j++) {
			if (board[i][j] != 6 && visited[i][j] == 0) cnt++;
		}
	}
	return cnt;
}



int simulation()
{
	// init
	memset(visited, 0, sizeof(visited));
	Q = {};


	for (int i = 0; i < V.size(); i++) {
		watch_CCTV(i, V[i].type, choice[i]);	// 어떤 종류 cctv 어느 방향으로 볼 것인지 
	}
	int cnt = cant_see_area();
	return cnt;
}



void DFS(int n)
{
	if (n == V.size()) {
		int res = simulation();
		if (res < ans) ans = res;
		return;
	}
	
	for (int p = 0; p < 4; p++) {
		choice[n] = p;
		DFS(n + 1);
	}
}


int main()
{
	input();
	DFS(0);	// 몇번째 cctv를 어떤 방향으로 감시할 것인지 ? 
	printf("%d\n", ans);
	return 0;
}

숙원사업 하나씩 또 해나가아는 중... 22

1. 테케를 보면서 순열/조합/중복순열/중복조합 중에 무엇을 써야하는지 파악했다. 

만약 2 / 2 / 5번 cctv가 있다면 같은 종류의 cctv이더라도 각각 어떤 방향을 보느냐에 따라 결과가 달라진다. 또한 문제의 테케를 보면같은 종류의 cctv가 같은 방향을 감시할 수도 있다. 따라서 "중복 순열"을 사용해야 한다. 

branch는 4(4방향) level은 cctv 개수로 하여 DFS를 돌려주었다. 

 

2. 다 정해지면 시뮬레이션을 돌린다. 이때 cctv 종류마다 한 방향만 감시할 수도 있고 두개 이상의 방향을 감시할 수도 있으므로 이에 대한 정보를 룩업테이블로 만들어 관리해주었다. 

-> 실수 1.. 처음 만들때 잘좀 만들자 ^^

 

3. 큐를 사용하여 감시할 수 있는 영역을 방문배열에 담아준다. 이때 주의해야 할 점은 방문된 곳을 건너뛰면 안된다. 

문제에서 "CCTV는 CCTV를 통과할 수 있다"고 했기 때문에, 방문처리는 해주되 BFS시 으레 사용하는 if(visited[nx][ny]) continue; 이렇게 스루해주면 안된다. 

-> 실수 2... 다른 종류 뿐 만 아니라 같은 종류의 cctv도 통과할 수있다. 문제좀 잘 읽자

 

4. 마지막으로 사각지대 개수를 세어준다. 벽이 아닌데(board[i][j] != 6) 방문하지 못한 곳(visited[i][j] == 0)은 사각지대이다. 해당 칸의 개수를 세어주면 된다.