문제
핵심
- cctv가 최대 8개이고, 4가지 방향을 가질 수 있다. 이므로 대략 이하의 알고리즘을 사용한다.
- 1번 cctv는 한 쪽 방향만 감시할 수 있고 2, 3번 cctv는 두 방향을 감시할 수 있다. cctv 번호마다 감시할 수 있는 영역이 다르고 90도씩 회전이 가능하게 이를 고려해서 구현해야 한다. 북, 동, 남, 서을 각 0, 1, 2, 3으로 두었을 때 가능한 감시 영역은 다음과 같다. 모든 감시 방향을 고려하여 감시할 수 없는 영역을 최소로 하는 값을 구한다.
{{0}, {1}, {2}, {3}}, // 1번 cctv
{{0, 2}, {1, 3}}, // 2번 cctv
{{0, 1}, {1, 2}, {2, 3}, {3, 0}}, // 3번 cctv
{{0, 1, 2}, {1, 2, 3}, {2, 3, 0}, {3, 0, 1}}, // 4번 cctv
{{0, 1, 2, 3}} // 5번 cctv- 감시 할 수 있는 경우는 dfs(재귀, 완전탐색)를 통해 구할 수 있다. 재귀의 종료조건은 cctv 다 골랐을 때이다. 예를 들어 1번 cctv와 2번 cctv가 있으면 1번 cctv 가능한 방향 (4개), 2번 cctv 가능한 방향 (2개) 총 8개의 경우를 탐색하여 seq 배열에 담는다. 코드로 나타내면 다음과 같다.
if (depth == (int)cctv.size()) {
// cctv 모든 방향이 확정
return;
}
for (auto& dir : cctvDir[type]) {
seq.push_back(dir);
dfs(depth + 1, seq);
seq.pop_back();
}개선
- 코드의 효율성을 조금 포기하여 구현을 간단하게 할 수 있다. 모든 경우의 수가 필요하고 각 경우가 독립적일 때 진법 변환 방식을 이용할 수 있다. 예를 들어 cctv가 2개이고, 가능한 방향이 4개일 때 총 , 16가지 경우가 존재한다. 진법 변환 방식을 이용해 가능한 순열을 표현하면 다음과 같다.
int n = 16;
for (int i = 0; i < n; ++i) {
int seq = i;
for (int cnt = 0; cnt < 2; ++cnt) {
cout << seq % 4 << ' ';
seq /= 4;
}
cout << '\n';
}0 0
1 0
2 0
3 0
0 1
1 1
2 1
3 1
0 2
1 2
2 2
3 2
0 3
1 3
2 3
3 3- 위의 방식으로 cctv의 모든 방향을 고려한 순열을 생성한 뒤 cctv 번호별로 적용이 가능하다. 예를 들어 1번 카메라는 1방향, 2번 카메라는 해당 방향과 마주 보는 방향(dir + 2), ... 5번 카메라는 해당 방향 + 나머지 3방향을 고려해서 단순화 할 수 있다. 코드로 나타내면 다음과 같다.
if (type == 1) {
watchArea(y, x, dir);
} else if (type == 2) {
watchArea(y, x, dir);
watchArea(y, x, (dir + 2) % 4);
} else if (type == 3) {
watchArea(y, x, dir);
watchArea(y, x, (dir + 1) % 4);
} else if (type == 4) {
watchArea(y, x, dir);
watchArea(y, x, (dir + 1) % 4);
watchArea(y, x, (dir + 3) % 4);
} else if (type == 5) {
watchArea(y, x, dir);
watchArea(y, x, (dir + 1) % 4);
watchArea(y, x, (dir + 2) % 4);
watchArea(y, x, (dir + 3) % 4);
}코드
시간복잡도
- 대략
C++
#include <iostream>
#include <vector>
using namespace std;
int n, m;
int room[14][14];
int cRoom[14][14];
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
int ans = 0x7fffffff;
vector<pair<int, int>> cctv;
vector<vector<vector<int>>> cctvDir = {
{},
{{0}, {1}, {2}, {3}},
{{0, 2}, {1, 3}},
{{0, 1}, {1, 2}, {2, 3}, {3, 0}},
{{0, 1, 2}, {1, 2, 3}, {2, 3, 0}, {3, 0, 1}},
{{0, 1, 2, 3}}
};
void WatchArea(int y, int x, int dir) {
while (true) {
y += dy[dir];
x += dx[dir];
if (y < 0 || x < 0 || y >= n || x >= m)
break;
if (cRoom[y][x] == 6)
break;
if (cRoom[y][x] >= 1 && cRoom[y][x] <= 5)
continue;
cRoom[y][x] = 9;
}
}
void dfs(int depth, vector<vector<int>>& seq) {
if (depth == (int)cctv.size()) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cRoom[i][j] = room[i][j];
}
}
for (int i = 0; i < (int)seq.size(); ++i) {
for (int j = 0; j < (int)seq[i].size(); ++j) {
WatchArea(cctv[i].first, cctv[i].second, seq[i][j]);
}
}
int cnt = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (cRoom[i][j] == 0)
++cnt;
}
}
ans = min(ans, cnt);
return;
}
int type = room[cctv[depth].first][cctv[depth].second];
for (auto& dir : cctvDir[type]) {
seq.push_back(dir);
dfs(depth + 1, seq);
seq.pop_back();
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> room[i][j];
if (room[i][j] >= 1 && room[i][j] <= 5)
cctv.push_back({i, j});
}
}
vector<vector<int>> seq;
dfs(0, seq);
cout << ans;
return 0;
}Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static int n, m;
static int[][] room = new int[14][14];
static int[][] cRoom = new int[14][14];
static int[] dy = {-1, 0, 1, 0};
static int[] dx = {0, 1, 0, -1};
static int ans = Integer.MAX_VALUE;
static ArrayList<int[]> cctv = new ArrayList<>();
static int[][][] cctvDir = {
{},
{{0}, {1}, {2}, {3}},
{{0, 2}, {1, 3}},
{{0, 1}, {1, 2}, {2, 3}, {3, 0}},
{{0, 1, 2}, {1, 2, 3}, {2, 3, 0}, {3, 0, 1}},
{{0, 1, 2, 3}}
};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
room[i][j] = Integer.parseInt(st.nextToken());
if (room[i][j] >= 1 && room[i][j] <= 5)
cctv.add(new int[]{i, j});
}
}
List<List<Integer>> seq = new ArrayList<>();
dfs(0, seq);
System.out.println(ans);
}
static void dfs(int depth, List<List<Integer>> seq) {
if (depth == cctv.size()) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cRoom[i][j] = room[i][j];
}
}
for (int i = 0; i < seq.size(); ++i) {
for (var dir : seq.get(i)) {
watchArea(cctv.get(i)[0], cctv.get(i)[1], dir);
}
}
int cnt = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (cRoom[i][j] == 0)
++cnt;
}
}
ans = Math.min(ans, cnt);
return;
}
int type = room[cctv.get(depth)[0]][cctv.get(depth)[1]];
for (var dir : cctvDir[type]) {
List<Integer> dirs = new ArrayList<>();
for (var e : dir)
dirs.add(e);
seq.add(dirs);
dfs(depth + 1, seq);
seq.remove(seq.size() - 1);
}
}
static void watchArea(int y, int x, Integer dir) {
while (true) {
y += dy[dir];
x += dx[dir];
if (y < 0 || x < 0 || y >= n || x >= m)
break;
if (cRoom[y][x] == 6)
break;
if (cRoom[y][x] >= 1 && cRoom[y][x] <= 5)
continue;
cRoom[y][x] = 9;
}
}
}
꾸준하게