[C++] 백준 15683 감시

문제 링크

---

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

15683번: 감시

 

 

접근 방법

---

아래와 같은 순서로 문제를 접근하였다.

1. CCTV의 타입(1~5), 좌표, 방향을 cctv 백터에 push

2. 모든 CCTV의 방향 조합 문제로 변형 -> 백트래킹 시도 (CCTV 타입도 고려해야함)

3. 백트래킹하며 CCTV의 타입과 방향, 좌표를 selected 벡터에 push

4. selected 크기가 cctv 전체 갯수 도달시 현재까지 선택된 CCTV 타입, 방향, 좌표 정보를 가지고

map에 감시 영역을 채운다.

5. 최소 사각지대의 개수를 반환한다.

 

단순히 따지자면 CCTV의 방향의 조합 문제인데, CCTV마다 한 번에 감시할 수 있는 방향이 다르기 때문에 CCTV 타입도 고려하면서 진행하였다.

 

방향에 대한 접근은 위와 같이 하였다. 타입 1 CCTV는 위와 같은 방향 접근으로 하며, 다른 타입도 위의 방향을 기반으로 정의하였다.

 

2번 타입은 위 사진과 같이 접근하였다. 정리하면 a번째 방향 + a+2번째 방향이다.

 

3번은 위와 같다. 정리하면 a번째 방향 + a+1번째 방향이다.

 

4번은 위와 같다. 정리하면 a번째 방향 + a-1번째 방향 + a + 1번째 방향이다.

 

5번은 모든 방향이다.

 

cctv의 정보를 담기 위해 구조체를 정의하였는데, CCTV의 타입, 방향, 좌표를 저장하였다.

각 CCTV 타입마다 방향의 개수가 다르므로 num_direct를 선언하였고, 방향에 대한 정보는 DIRECTION에 담았다.

typedef struct cctv {
	int type;
	int direct;
	int y, x;
};
int num_direct[NUM_TYPE] = { 0, 4, 2, 4, 4, 1 }; // 1번: 4개, 2번: 2개, 3번: 4개, 4번: 2개, 5번: 1개
const coord DIRECTION[4] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };

 

위의 방향 접근법으로 해당 방향 라인을 체크해주는 함수를 정의하였다.

(여기서 tmp는 map의 복사본입니다.)

void fill_line(vector<vector<int>> &tmp, int sy, int sx, int direct) {
	while (isRanged(sy, sx) && map[sy][sx] != 6) {
		tmp[sy][sx] = 9;
		sy += DIRECTION[direct].y;
		sx += DIRECTION[direct].x;
	}
}

위의 함수는 tmp라는 2차원 배열에 시작 위치 (sy,sx)를 기준으로 direct 방향으로 모든 영역을 9로 표시한다. (벽을 만나면 멈춤)

위 함수를 이용하여 cctv의 타입에 따라서 map을 칠해주는 함수를 정의하였다. 내용은 아래와 같다.

void fill_map(vector<vector<int>> &tmp, cctv c) {
	if (c.type == 1) {
		fill_line(tmp, c.y, c.x, c.direct);
	}
	else if (c.type == 2) {
		fill_line(tmp, c.y, c.x, c.direct);
		fill_line(tmp, c.y, c.x, c.direct + 2);
	}
	else if (c.type == 3) {
		fill_line(tmp, c.y, c.x, c.direct);
		fill_line(tmp, c.y, c.x, (c.direct + 1) % 4);
	}
	else if (c.type == 4) {
		fill_line(tmp, c.y, c.x, c.direct);
		fill_line(tmp, c.y, c.x, (c.direct == 0 ? 3 : c.direct - 1));
		fill_line(tmp, c.y, c.x, (c.direct + 1) % 4);
	}
	else {
		for (int direct = 0; direct < 4; ++direct)
			fill_line(tmp, c.y, c.x, direct);
	}
}

위 함수는 tmp라는 2차원 배열을 받아서 cctv type c와 방향에 따라서 map에 감시 구역을 표시해주는 함수이다.

 

소스 코드

---

#include <vector>
#include <climits>
#include <iostream>
#include <algorithm>
#define MAX 8
#define NUM_TYPE 6
using namespace std;
typedef struct cctv {
	int type;
	int direct;
	int y, x;
};
typedef struct coord {
	int y, x;
};
int N, M;
vector<vector<int>> map(MAX, vector<int>(MAX, 0)), tmp(MAX, vector<int>(MAX, 0));
vector<cctv> cctv_list, selected;
int num_direct[NUM_TYPE] = { 0, 4, 2, 4, 4, 1 }; // 1번: 4개, 2번: 2개, 3번: 4개, 4번: 2개, 5번: 1개
const coord DIRECTION[4] = { {-1, 0}, {0, 1}, {1, 0}, {0, -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) {
				cctv_list.push_back({map[i][j], 0, i, j}); // {CCTV종류, 방향, y좌표, x좌표}
			}
		}
	}
}

bool isRanged(int y, int x) {
	if (y >= N || x >= M || y < 0 || x < 0) return false;
	return true;
}

void fill_line(vector<vector<int>> &tmp, int sy, int sx, int direct) {
	while (isRanged(sy, sx) && map[sy][sx] != 6) {
		tmp[sy][sx] = 9;
		sy += DIRECTION[direct].y;
		sx += DIRECTION[direct].x;
	}
}

void fill_map(vector<vector<int>> &tmp, cctv c) {
	if (c.type == 1) {
		fill_line(tmp, c.y, c.x, c.direct);
	}
	else if (c.type == 2) {
		fill_line(tmp, c.y, c.x, c.direct);
		fill_line(tmp, c.y, c.x, c.direct + 2);
	}
	else if (c.type == 3) {
		fill_line(tmp, c.y, c.x, c.direct);
		fill_line(tmp, c.y, c.x, (c.direct + 1) % 4);
	}
	else if (c.type == 4) {
		fill_line(tmp, c.y, c.x, c.direct);
		fill_line(tmp, c.y, c.x, (c.direct == 0 ? 3 : c.direct - 1));
		fill_line(tmp, c.y, c.x, (c.direct + 1) % 4);
	}
	else {
		for (int direct = 0; direct < 4; ++direct)
			fill_line(tmp, c.y, c.x, direct);
	}
}

int count_area(vector<vector<int>> &tmp) {
	int ret = 0;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			if (tmp[i][j] == 0) ++ret;
		}
	}
	return ret;
}

vector<vector<int>> copy_map(vector<vector<int>> &from, vector<vector<int>> &to) {
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			to[i][j] = from[i][j];
		}
	}
	return to;
}

int nCm(int cnt, int prev) {
	if (cnt == cctv_list.size()) {
		tmp = copy_map(map, tmp);
		for (int i = 0; i < selected.size(); ++i)
			fill_map(tmp, selected[i]);
		int ret = count_area(tmp);
		return ret;
	}
	int ret = INT_MAX;
	for (int next = prev + 1; next < cctv_list.size(); ++next) {
		for (int direct = 0; direct < num_direct[cctv_list[next].type]; ++direct) {
			selected.push_back({cctv_list[next].type, direct, cctv_list[next].y, cctv_list[next].x});// 현재 cctv type, direct를 저장한다.
			ret = min (ret, nCm(cnt + 1, next));
			selected.pop_back();// 칠한 map을 다시 되돌린다.
		}
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	input();
	cout << nCm(0, -1);
	return 0;
}

 

개발 환경은 VS 2019입니다.

질문, 지적, 덧글 환영합니다!!