{4,2,4,4,1}
가지의 방향을 가지고 있으며 이 경우를 모두 탐색해주어야 한다👩💻1. input Data
- 사무실에 있는 벽과 cctv에 관한 정보를 입력받을 때, cctv는
vector<CCTV> cctv
에 저장해준다.struct CCTV
에는 cctv의(y,x)
좌표와 cctv의 번호가 저장된다.struct CCTV { int y, x, idx; }; vector<CCTV> cctv;
for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cin >> office[i][j]; if (office[i][j] >= 1 && office[i][j] <= 5) cctv.push_back({ i, j, office[i][j] }); } }
👩💻2. 각 방향으로의 감시
- 위에서 나타냈던 각 cctv의 모든 방향을 따로 정의하지 않고 감시할 방향
d
를 인자로 보내면d
에 따라 동(0)서(1)남(2)북(3)으로 감시한다.
예를 들어 5번 cctv가 있을 경우, 동서남북 방향으로 4번 함수를 호출한다.vector<vector<int>> inspectArea(vector<vector<int>> tmp, int d, int r, int c)
① tmp: 현재 사무실의 상태를 담은 이차원 벡터
② d: 감시할 방향
③ (r,c): 현재 cctv의 좌표- 동쪽(0)방향으로의 감시만 예로 들어보면, y좌표는 변함이 없고 x좌표가 사무실을 벗어나지 않고 벽이 아닐 때까지 감시한다
if (d == 0) { int j = c + 1; while (j < M && tmp[r][j] != WALL) { tmp[r][j++] = INSPECT; } }
👩💻3. dfs 함수 구현
void dfs(int L, vector<vector<int>> office)
L
은 cctv의 갯수와 같아질 때까지 반복하다가 같아지면office
에서 빈 공간의 갯수를 구하여 최솟값을 갱신한다if (L == cctv.size()) { int cnt = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (office[i][j] == EMPTY) cnt++; } } minCnt = min(minCnt, cnt); return; }
L
번째 cctv의 정보를 보고cIdx
즉, 어떤 cctv냐에 따라서 cctv가 감시해야 하는 영역을 탐색한다int cy = cctv[L].y; int cx = cctv[L].x; int cIdx = cctv[L].idx;
- 가장 복잡한 4번 cctv를 예로 들어보자
else if (cIdx == 4) { for (int i = 0; i < 4; i++) { tmp = office; for (int j = 0; j < 4; j++) { if (i == j) continue; tmp = inspectArea(tmp, j, cy, cx); } dfs(L + 1, tmp); } }
총 4번 각각 다른 모양을 만들어야하고, 각 모양마다 3방향이 있기 때문에 3번
inspectArea
를 호출해서 현재 사무실의 상태를 담은tmp
를 다시 재귀호출한다.
전체코드
#include <iostream> #include <vector> #include <cmath> using namespace std; const int EMPTY = 0; const int WALL = 6; const int INSPECT = -1; int minCnt = 64; int N, M; int dy[] = { 0,0,1,-1 }; int dx[] = { 1,-1,0,0 }; struct CCTV { int y, x, idx; }; vector<CCTV> cctv; vector<vector<int>> inspectArea(vector<vector<int>> tmp, int d, int r, int c) { if (d == 0) { int j = c + 1; while (j < M && tmp[r][j] != WALL) { tmp[r][j++] = INSPECT; } } else if (d == 1) { int j = c - 1; while (j >= 0 && tmp[r][j] != WALL) { tmp[r][j--] = INSPECT; } } else if (d == 2) { int i = r + 1; while (i < N && tmp[i][c] != WALL) { tmp[i++][c] = INSPECT; } } else if (d == 3) { int i = r -1; while (i>=0 && tmp[i][c] != WALL) { tmp[i--][c] = INSPECT; } } return tmp; } void dfs(int L, vector<vector<int>> office) { if (L == cctv.size()) { int cnt = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (office[i][j] == EMPTY) cnt++; } } minCnt = min(minCnt, cnt); return; } vector<vector<int>>tmp; int cy = cctv[L].y; int cx = cctv[L].x; int cIdx = cctv[L].idx; if (cIdx == 1) { for (int i = 0; i < 4; i++) { dfs(L + 1, inspectArea(office, i, cy, cx)); } } else if (cIdx == 2) { tmp = inspectArea(office, 0, cy, cx); tmp = inspectArea(tmp, 1, cy, cx); dfs(L + 1, tmp); tmp = inspectArea(office, 2, cy, cx); tmp = inspectArea(tmp, 3, cy, cx); dfs(L + 1, tmp); } else if (cIdx == 3) { tmp = inspectArea(office, 0, cy, cx); tmp = inspectArea(tmp, 3, cy, cx); dfs(L + 1, tmp); tmp = inspectArea(office, 2, cy, cx); tmp = inspectArea(tmp, 1, cy, cx); dfs(L + 1, tmp); tmp = inspectArea(office, 1, cy, cx); tmp = inspectArea(tmp, 3, cy, cx); dfs(L + 1, tmp); tmp = inspectArea(office, 0, cy, cx); tmp = inspectArea(tmp, 2, cy, cx); dfs(L + 1, tmp); } else if (cIdx == 4) { for (int i = 0; i < 4; i++) { tmp = office; for (int j = 0; j < 4; j++) { if (i == j) continue; tmp = inspectArea(tmp, j, cy, cx); } dfs(L + 1, tmp); } } else if (cIdx == 5) { tmp = office; for (int i = 0; i < 4; i++) tmp = inspectArea(tmp, i, cy, cx); dfs(L + 1, tmp); } } void input() { cin >> N >> M; vector<vector<int>> office = vector<vector<int>>(N, vector<int>(M)); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cin >> office[i][j]; if (office[i][j] >= 1 && office[i][j] <= 5) cctv.push_back({ i, j, office[i][j] }); } } dfs(0, office); } int main() { input(); cout << minCnt << endl; return 0; }