BJ15683 감시
https://www.acmicpc.net/problem/15683
이 문제는 벽과 5가지의 CCTV가 입력으로 주어지고, 씨씨티비의 방향을 적절히 정해 사각지대의 최소 크기를 구하는 것이다.
CCTV를 배열에 담아두고, 각 씨씨티비의 방향을 돌려가며 모든 경우의 수를 탐색하는 방식으로 구현했다.
package day0218;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class CCTV {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer st;
static tv[] tvs;
static int[][] dir = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
static int N, M, cnt_tv, answer = Integer.MAX_VALUE;
static public class tv {
int x, y;
int state;
public tv(int x, int y, int state) {
this.x = x;
this.y = y;
this.state = state;
}
}
static int check_blind(int[][] map) {
int count = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 0)
count++;
}
}
return count;
}
static void solve(int[][] map, int n_tv) {
if (n_tv == cnt_tv) {
int tmp = check_blind(map);
// print(map);
// System.out.println();
if (tmp < answer) {
answer = tmp;
}
return;
}
switch (tvs[n_tv].state) { // CCTV의 번호에 따라 경우의수만큼 재귀함수를 호출.
case 1:
for (int d = 0; d < 4; d++) {
int[][] nextmap = beam(map, tvs[n_tv].x, tvs[n_tv].y, d);
solve(nextmap, n_tv + 1);
}
break;
case 2:
for (int cas = 0; cas < 2; cas++) {
if (cas == 0) {
int[][] nextmap = beam(map, tvs[n_tv].x, tvs[n_tv].y, 0);
nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 1);
solve(nextmap, n_tv + 1);
} else {
int[][] nextmap = beam(map, tvs[n_tv].x, tvs[n_tv].y, 2);
nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 3);
solve(nextmap, n_tv + 1);
}
}
break;
case 3:
for (int cas = 0; cas < 4; cas++) {
if (cas == 0) {
int[][] nextmap = beam(map, tvs[n_tv].x, tvs[n_tv].y, 0);
nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 2);
solve(nextmap, n_tv + 1);
} else if (cas == 1) {
int[][] nextmap = beam(map, tvs[n_tv].x, tvs[n_tv].y, 0);
nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 3);
solve(nextmap, n_tv + 1);
} else if (cas == 2) {
int[][] nextmap = beam(map, tvs[n_tv].x, tvs[n_tv].y, 1);
nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 2);
solve(nextmap, n_tv + 1);
} else if (cas == 3) {
int[][] nextmap = beam(map, tvs[n_tv].x, tvs[n_tv].y, 1);
nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 3);
solve(nextmap, n_tv + 1);
}
}
break;
case 4:
for (int cas = 0; cas < 4; cas++) {
if (cas == 0) {
int[][] nextmap = beam(map, tvs[n_tv].x, tvs[n_tv].y, 1);
nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 2);
nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 3);
solve(nextmap, n_tv + 1);
} else if (cas == 1) {
int[][] nextmap = beam(map, tvs[n_tv].x, tvs[n_tv].y, 0);
nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 2);
nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 3);
solve(nextmap, n_tv + 1);
} else if (cas == 2) {
int[][] nextmap = beam(map, tvs[n_tv].x, tvs[n_tv].y, 0);
nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 1);
nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 3);
solve(nextmap, n_tv + 1);
} else if (cas == 3) {
int[][] nextmap = beam(map, tvs[n_tv].x, tvs[n_tv].y, 0);
nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 1);
nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 2);
solve(nextmap, n_tv + 1);
}
}
break;
case 5:
int[][] nextmap = beam(map, tvs[n_tv].x, tvs[n_tv].y, 0);
nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 1);
nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 2);
nextmap = beam(nextmap, tvs[n_tv].x, tvs[n_tv].y, 3);
solve(nextmap, n_tv + 1);
break;
}
}
static int[][] beam(int[][] map, int x, int y, int d) { // CCTV가 감시하는 부분을 맵에 색칠함. int d에 따라 동, 서, 남, 북.
int[][] tmp_map = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
tmp_map[i][j] = map[i][j];
}
}
while (x >= 0 && x < N && y >= 0 && y < M) {
if (map[x][y] == 6) {
break;
}
tmp_map[x][y] = 9; // 감시구역이면 9로 초기화.
x += dir[d][0];
y += dir[d][1];
}
return tmp_map;
}
static void print(int[][] map) { // 맵을 출력.
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
System.out.print(map[i][j]);
}
System.out.println();
}
}
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int[][] map = new int[N][M];
cnt_tv = 0;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if (map[i][j] > 0 && map[i][j] < 6) {
cnt_tv++;
}
}
}
tvs = new tv[cnt_tv];
int c = 0;
for (int i = 0; i < N; i++) { // CCTV의 정보를 tvs 배열에 담음.
for (int j = 0; j < M; j++) {
if (map[i][j] > 0 && map[i][j] < 6) {
tvs[c++] = new tv(i, j, map[i][j]);
}
}
}
solve(map, 0);
System.out.println(answer);
}
}
Author And Source
이 문제에 관하여(BJ15683 감시), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mraz0210/BJ15683-감시저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)