[백준][15683번] 감시

Algorithm/백준

[백준][15683번] 감시

1일1코딩 2020. 4. 26. 22:40

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

15683번: 감시

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할

www.acmicpc.net

풀이과정

1. cctv의 종류는 5가지이며, 각 각 회전이 가능하며(90도), 종류마다 감시 가능한 라인이 다르다.

2. 따라서 cctv별로 어떤 라인을 감시하는지에 대한 lineCheck함수를 만들었다.

3. lineDraw는 감시영역을 그리는 함수이다. (cctv는 벽을 제외하고는 통과가 된다. 처음에 cctv또한 통과가 안된다 생각해서 틀렸다.. 문제를 꼼꼼히 읽자)

4. 이제 입력 받은 카메라 별로 각 회전을 통해 모든 방향을 검사하고 가장 적은 사각지대를 가지는 결과를 만들어준다.

소스코드(완전탐색)

#include <stdio.h>
#include <vector>
#include <string.h>
using namespace std;
enum DIRECTION { EAST, WEST, SOUTH, NORTH };
struct cctv {
	int x;
	int y;
	int type;
}typedef cctv;
vector<cctv> v;
int N, M, answer;
int map[8][8];
int type[5] = {4, 2, 4, 4, 1 };
int dx[4] = { 1, -1 , 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

void lineDraw(cctv cam, int d) {
	int x = cam.x;
	int y = cam.y;
	while (1) {
		int nx = x + dx[d];
		int ny = y + dy[d];
		if (nx < 0 || ny < 0 || nx >= M || ny >= N || map[ny][nx] == 6) return;
		map[ny][nx] = -1;
		x = nx;
		y = ny;
	}
}

void lineCheck(cctv cam, int d)
{
	if (cam.type == 1) {
		lineDraw(cam, d);
	}
	else if (cam.type == 2) {
		if (d == 0) {
			lineDraw(cam, EAST);
			lineDraw(cam, WEST);
		}
		else {
			lineDraw(cam, SOUTH);
			lineDraw(cam, NORTH);
		}
	}
	else if (cam.type == 3) {
		switch (d) {
		case 0: lineDraw(cam, NORTH); lineDraw(cam, EAST); break;
		case 1: lineDraw(cam, EAST); lineDraw(cam, SOUTH); break;
		case 2: lineDraw(cam, SOUTH); lineDraw(cam, WEST); break;
		case 3: lineDraw(cam, WEST); lineDraw(cam, NORTH); break;
		}
	}
	else if (cam.type == 4) {
		switch (d) {
		case 0: lineDraw(cam, WEST); lineDraw(cam, NORTH); lineDraw(cam, EAST); break;
		case 1: lineDraw(cam, NORTH); lineDraw(cam, EAST); lineDraw(cam, SOUTH); break;
		case 2: lineDraw(cam, EAST); lineDraw(cam, SOUTH); lineDraw(cam, WEST); break;
		case 3: lineDraw(cam, SOUTH); lineDraw(cam, WEST); lineDraw(cam, NORTH); break;
		}
	}
	else {
		for (int i = 0; i < 4; i++) {
			lineDraw(cam, i);
		}
	}
}

void solution(int depth)
{
	if (answer == 0) {
		return;
	}
	if (depth == v.size()) {
		int sum = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] != 0) continue;
				sum++;
			}
		}
		if (answer > sum) {
			answer = sum;
		}
		return;
	}
	int cpymap[8][8];
	memcpy(cpymap, map, sizeof(cpymap));
	for (int i = 0; i < type[v[depth].type - 1]; i++) {
		lineCheck(v[depth], i);
		solution(depth + 1);
		memcpy(map, cpymap, sizeof(map));
	}
}

int main()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] >= 1 && map[i][j] <= 5) {
				cctv cam = { j, i, map[i][j] };
				v.push_back(cam);
			}
		}
	}
	answer = N * M;
	solution(0);
	printf("%d\n", answer);
}

결과

6개월전 풀었던 소스와는 다르게 풀어서 참고용으로 넣었다. 좀 복잡하게 푼 것 같다.

소스코드 (완전탐색 + 스택)

#include <stdio.h>
#include <string.h>
#include <vector>
#include <stack>
using namespace std;

struct node {
	int x;
	int y;
	int d;
}typedef node;

struct item {
	int num;
	int d;
	int x;
	int y;
}typedef cctv;
int map[8][8];

vector<node> v;
stack<cctv> st;
int dx1[] = { 1, 0, -1, 0 };
int dy1[] = { 0, 1, 0, -1 };
int dx2[2][2] = { {1, -1}, { 0, 0} };
int dy2[2][2] = { {0, 0}, { 1, -1} };
int dx3[4][2] = { {1, 0}, {1, 0}, {0, -1}, {-1, 0} };
int dy3[4][2] = { {0, -1}, {0,1}, {1, 0}, {0, -1} };
int dx4[4][3] = { {-1, 0, 1} ,{0, 1, 0}, {-1, 0 ,1},{0, -1, 0} };
int dy4[4][3] = { {0 , -1, 0},{-1, 0, 1},{0, 1, 0}, {-1, 0, 1} };
int dx5[] = { 1, -1 ,0, 0 };
int dy5[] = { 0, 0, -1, 1 };
int answer = 0;
int N, M;
int directionXY(int num, int d, int XY, int dd)
{
	if (num == 1) {
		return XY == 0 ? dx1[d] : dy1[d];
	}
	else if (num == 2) {
		return XY == 0 ? dx2[d][dd] : dy2[d][dd];
	}
	else if (num == 3) {
		return XY == 0 ? dx3[d][dd] : dy3[d][dd];
	}
	else if (num == 4) {
		return XY == 0 ? dx4[d][dd] : dy4[d][dd];
	}
	else {
		return XY == 0 ? dx5[dd] : dy5[dd];
	}
}
void move()
{
	int _map[8][8];
	memcpy(_map, map, sizeof(_map));
	stack<cctv> _st = st;
	while (!_st.empty()) {
		cctv c = _st.top(); _st.pop();
		int rotate = 0;
		// 1 -> 4 , 2 -> 2 , 3-> 4, 4->4 5 -> 1
		switch (c.num)
		{
		case 1: rotate = 1; break;
		case 3: rotate = 2; break;
		case 4: rotate = 3; break;
		case 2: rotate = 2; break;
		case 5: rotate = 4; break;
		default:
			break;
		}
		for (int i = 0; i < rotate; i++) {
			int _y = c.y;
			int _x = c.x;
			int dx = directionXY(c.num, c.d, 0, i);
			int dy = directionXY(c.num, c.d, 1, i);
			while (1) {
				int nextX = _x + dx;
				int nextY = _y + dy;
				if (_map[nextY][nextX] == 6) {
					break;
				}
				else {
					if (nextX >= 0 && nextX < M && nextY >= 0 && nextY < N) {
						_y = nextY;
						_x = nextX;
						_map[_y][_x] = -1;
					}
					else {
						break;
					}
				}
			}
		}
	}

	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (_map[i][j] == 0) {
				cnt++;
			}
		}
	}

	if (answer > cnt) {
		answer = cnt;
	}
}

void solution(int count)
{
	if (v.size() == st.size()) {
		move();
		return;
	}

	node n = v[count];
	int rotate = 0;
	// 1 -> 4 , 2 -> 2 , 3-> 4, 4->4 5 -> 1
	switch (n.d)
	{
	case 1: case 3: case 4: rotate = 4; break;
	case 2: rotate = 2; break;
	case 5: rotate = 1; break;
	default:
		break;
	}

	for (int i = 0; i < rotate; i++) {
		cctv c = { n.d, i ,n.x, n.y};
		st.push(c);
		solution(count+1);
		st.pop();
	}
	
}

int main()
{
	scanf("%d %d", &N, &M);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] > 0 && map[i][j] < 6) {
				node n = { j, i, map[i][j] };
				v.push_back(n);
			}
		}
	}
	answer = N * M;
	solution(0);
	printf("%d\n", answer);

}

결과