문제 설명
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감
www.acmicpc.net
접근 방법
해당 문제에서는 각각의 CCTV의 동작별로 사무실을 감시했을 때 해당 사무실의 사각지대가 가장 최소일 때의 값을 요구하고 있습니다.
우선 5개의 CCTV별로 각각의 동작 방식들을 구현했습니다. 기본적으로 모든 CCTV는 동, 서, 남, 북 일직선 방향으로 감시를 할 수 있으므로 기본적인 동작들을 구현한 뒤 각각의 CCTV별로 이 동작들을 활용하도록 했습니다.
이후 사무실 데이터를 입력받을 때 CCTV 정보들을 List에 저장시켰습니다. 이를 활용하여 백트래킹을 통해 각각의 CCTV가 자기 자신의 방식대로 회전시킬 수 있는 모든 경우의 수를 고려해주면서 사각지대를 최솟값을 구하도록 했습니다.
이때 백트래킹을 할 때 스택을 활용했는데 이는 CCTV 감시 동작 이후 다음 경우의 수를 고려해줄 때 이전 사무실 데이터를 기억하기 위함입니다. CCTV 방향 설정 전에 사무실 데이터를 저장(push)해놨다가 해당 CCTV의 감시 동작이 마무리되면 이전 데이터를 꺼내오고(pop) 다시 다음 CCTV의 감시 동작을 진행하도록 했습니다.
전체 소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;
class Main {
static int[][] office, origin;
static int n, m, result = 64;
static List<CCTV> cctvs = new ArrayList<>();
static Stack<int[][]> logs = new Stack<>();
static class CCTV {
int x;
int y;
int cctvNumber;
public CCTV(int x, int y, int cctvNumber) {
this.x = x;
this.y = y;
this.cctvNumber = cctvNumber;
}
}
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());
office = new int[n][m];
origin = new int[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
office[i][j] = Integer.parseInt(st.nextToken());
origin[i][j] = office[i][j];
if (office[i][j] >= 1 && office[i][j] <= 5) {
cctvs.add(new CCTV(i, j, office[i][j]));
}
}
}
runCCTV(0);
System.out.println(result);
}
private static void runCCTV(int depth) {
if (depth == cctvs.size()) {
verify();
return;
}
CCTV c = cctvs.get(depth);
int cctvNumber = c.cctvNumber, x = c.x, y = c. y;
if (cctvNumber == 1) {
for (int i = 0; i < 4; i++) {
copy();
observe1(x, y, i);
runCCTV(depth + 1);
office = logs.pop();
}
} else if (cctvNumber == 2) {
for (int i = 0; i < 2; i++) {
copy();
observe2(x, y, i);
runCCTV(depth + 1);
office = logs.pop();
}
} else if (cctvNumber == 3) {
for (int i = 0; i < 4; i++) {
copy();
observe3(x, y, i);
runCCTV(depth + 1);
office = logs.pop();
}
} else if (cctvNumber == 4) {
for (int i = 0; i < 4; i++) {
copy();
observe4(x, y, i);
runCCTV(depth + 1);
office = logs.pop();
}
} else if (cctvNumber == 5) {
copy();
observe5(x, y);
runCCTV(depth + 1);
office = logs.pop();
}
}
private static void copy() {
int[][] office = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
office[i][j] = Main.office[i][j];
}
}
logs.push(office);
}
private static void observe1(int x, int y, int direction) {
if (direction == 0) {
observeRight(x, y);
} else if (direction == 1) {
observeDown(x, y);
} else if (direction == 2) {
observeLeft(x, y);
} else if (direction == 3) {
observeUp(x, y);
}
}
private static void observe2(int x, int y, int direction) {
if (direction == 0) {
observeRight(x, y);
observeLeft(x, y);
} else if (direction == 1) {
observeDown(x, y);
observeUp(x, y);
}
}
private static void observe3(int x, int y, int direction) {
if (direction == 0) {
observeUp(x, y);
observeRight(x, y);
} else if (direction == 1) {
observeRight(x, y);
observeDown(x, y);
} else if (direction == 2) {
observeDown(x, y);
observeLeft(x, y);
} else if (direction == 3) {
observeLeft(x, y);
observeUp(x, y);
}
}
private static void observe4(int x, int y, int direction) {
if (direction == 0) {
observeLeft(x, y);
observeUp(x, y);
observeRight(x, y);
} else if (direction == 1) {
observeUp(x, y);
observeRight(x, y);
observeDown(x, y);
} else if (direction == 2) {
observeRight(x, y);
observeDown(x, y);
observeLeft(x, y);
} else if (direction == 3) {
observeDown(x, y);
observeLeft(x, y);
observeUp(x, y);
}
}
private static void observe5(int x, int y) {
observeRight(x, y);
observeDown(x, y);
observeLeft(x, y);
observeUp(x, y);
}
private static void observeRight(int x, int y) {
for (int i = y + 1; i < m; i++) {
if (office[x][i] == 6) {
break;
}
if (office[x][i] == 0) {
office[x][i] = 7;
}
}
}
private static void observeLeft(int x, int y) {
for (int i = y - 1; i > -1; i--) {
if (office[x][i] == 6) {
break;
}
if (office[x][i] == 0) {
office[x][i] = 7;
}
}
}
private static void observeUp(int x, int y) {
for (int i = x - 1; i > -1; i--) {
if (office[i][y] == 6) {
break;
}
if (office[i][y] == 0) {
office[i][y] = 7;
}
}
}
private static void observeDown(int x, int y) {
for (int i = x + 1; i < n; i++) {
if (office[i][y] == 6) {
break;
}
if (office[i][y] == 0) {
office[i][y] = 7;
}
}
}
private static void verify() {
int temp = 0;
for (int j = 0; j < n; j++) {
for (int k = 0; k < m; k++) {
if (office[j][k] == 0) {
temp++;
}
}
}
result = Math.min(result, temp);
}
}
참고자료
- https://www.acmicpc.net/problem/15683
'Algorithm > BOJ' 카테고리의 다른 글
| [백준 - 9663] N-Queen - Java (0) | 2022.07.15 |
|---|---|
| [백준 - 14889] 스타트와 링크 - Java (0) | 2022.07.14 |
| [백준 - 25330] SHOW ME THE DUNGEON - Java (0) | 2022.07.10 |
| [백준 - 1713] 후보자 추천 - Java (0) | 2022.06.03 |
| [백준 - 2468] 안전 영역 - Java (0) | 2022.05.23 |