Algorithm/Acmicpc
15683 감시 [JAVA]
시롱시롱
2024. 10. 28. 23:26
문제 분석
https://www.acmicpc.net/problem/15683
n*m 배열이 주어진다. 각 배열의 원소는 값에 따라 아래의 역할을 한다.
0 : 빈 땅
1~5 : CCTV
6 : 벽
각 CCTV는 1~5의 값에 따라 감시할 수 있는 방향의 유형이 정해져있고, 특정 방향으로 바라보는 CCTV는 배열의 끝 혹은 벽을 만나기전까지 감시를 할 수 있다.
CCTV의 방향은 아래와 같다.
CCTV는 90도씩 회전할 수 있다.
이때, CCTV들을 특정 각도로 회전시키며 배열을 감시할 때 사각지대의 최솟값을 구하는게 문제다.
여기서 주의할 점은, 벽과 CCTV가 존재하는 곳은 사각지대로 세지 않는다.
문제를 객체지향적으로 접근한다면, 즉 조금 더 세분화해서 쪼개보면 각 CCTV를 조금 더 단순하게 표현할 수 있다.
1 -> 동,서,남,북 중 하나의 방향을 비춘다
2 -> 동-서, 남-북 중 하나의 방향을 비춘다
3 -> 북-동, 동-남, 남-서, 서-북 중 하나의 방향을 비춘다.
4 -> 서-북-동, 북-동-남, 동-남-서, 남-서-북 중 하나의 방향을 비춘다.
5 -> 동-서-남-북을 비춘다.
동,서,남,북에 대해 비추는 방향에 따라 볼 수 있는 (사각지대를 없앨 수 있는) 점은 독립이기에 해당 기능을 별도의 메소드로 각각 만들어 이를 엮어서 사용할 수 있다.
따라서, 나는 BFS로 각 CCTV를 순서대로 탐색하고
각 CCTV의 타입에 따라 비출 수 있는 방향의 경우의 수에 대해 동,서,남,북을 비추는 메소드를 이용하여 새롭게 비춰진 점들을 구하고
다음 depth로 넘어가는 것을 반복한다.
그렇게 모든 CCTV에 대해 반복을 마쳤다면 그 상태의 배열의 사각지대의 수를 세고 이를 최솟값과 비교하여 저장한다.
다시 돌아와서는 설정한 방향의 점들을 revert 하고 다음 방향으로 cctv를 돌려 다시 다음 depth를 탐색한다.
위 과정을 수행하는 BFS를 수행하게 된다면 결국에는 모든 CCTV가 비출 수 있는 모든 방향에 대해 사각지대의 수를 계산할 수 있게 된다.
코드
import java.text.ParsePosition;
import java.util.*;
public class Main {
static int[][] board;
static List<CCTV> cctvList;
static int minHiddenCount;
static int n,m;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
board = new int[n][m];
cctvList = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
board[i][j] = sc.nextInt();
if(board[i][j] >= 1 && board[i][j] <=5){
cctvList.add(new CCTV(new Point(i,j),board[i][j]));
}
}
}
minHiddenCount = n*m;
findAllRoot(0);
System.out.println(minHiddenCount);
}
static void findAllRoot(int nowIdx){
if(nowIdx >= cctvList.size()){
minHiddenCount = Math.min(minHiddenCount, countHiddenPoints());
return;
}
CCTV cctv = cctvList.get(nowIdx);
Set<Point> upPoints = seeUpward(cctv.point);
Set<Point> downPoints = seeDownward(cctv.point);
Set<Point> rightPoints = seeRightward(cctv.point);
Set<Point> leftPoints = seeLeftward(cctv.point);
switch (cctv.type){
case 1:
markPoints(upPoints);
findAllRoot(nowIdx+1);
revertPoints(upPoints);
markPoints(downPoints);
findAllRoot(nowIdx+1);
revertPoints(downPoints);
markPoints(rightPoints);
findAllRoot(nowIdx+1);
revertPoints(rightPoints);
markPoints(leftPoints);
findAllRoot(nowIdx+1);
revertPoints(leftPoints);
break;
case 2:
markPoints(upPoints);
markPoints(downPoints);
findAllRoot(nowIdx+1);
revertPoints(upPoints);
revertPoints(downPoints);
markPoints(rightPoints);
markPoints(leftPoints);
findAllRoot(nowIdx+1);
revertPoints(rightPoints);
revertPoints(leftPoints);
break;
case 3:
markPoints(upPoints);
markPoints(rightPoints);
findAllRoot(nowIdx+1);
revertPoints(upPoints);
markPoints(downPoints);
findAllRoot(nowIdx+1);
revertPoints(rightPoints);
markPoints(leftPoints);
findAllRoot(nowIdx+1);
revertPoints(downPoints);
markPoints(upPoints);
findAllRoot(nowIdx+1);
revertPoints(leftPoints);
revertPoints(upPoints);
break;
case 4:
markPoints(leftPoints);
markPoints(upPoints);
markPoints(rightPoints);
findAllRoot(nowIdx+1);
revertPoints(leftPoints);
markPoints(downPoints);
findAllRoot(nowIdx+1);
revertPoints(upPoints);
markPoints(leftPoints);
findAllRoot(nowIdx+1);
revertPoints(rightPoints);
markPoints(upPoints);
findAllRoot(nowIdx+1);
revertPoints(upPoints);
revertPoints(downPoints);
revertPoints(leftPoints);
break;
case 5:
markPoints(leftPoints);
markPoints(upPoints);
markPoints(rightPoints);
markPoints(downPoints);
findAllRoot(nowIdx+1);
revertPoints(upPoints);
revertPoints(downPoints);
revertPoints(leftPoints);
revertPoints(rightPoints);
break;
default:
throw new RuntimeException("Impossible type");
}
}
static Set<Point> seeUpward(Point point){
Set<Point> addedPoints = new HashSet<>();
for(int i = point.x-1; i >= 0; i--){
if(board[i][point.y] == 6)
break;
if(board[i][point.y] == 0)
addedPoints.add(new Point(i, point.y));
}
return addedPoints;
}
static Set<Point> seeDownward(Point point){
Set<Point> addedPoints = new HashSet<>();
for(int i = point.x+1; i < n; i++){
if(board[i][point.y] == 6)
break;
if(board[i][point.y] == 0)
addedPoints.add(new Point(i, point.y));
}
return addedPoints;
}
static Set<Point> seeRightward(Point point){
Set<Point> addedPoints = new HashSet<>();
for(int i = point.y+1; i < m; i++){
if(board[point.x][i] == 6)
break;
if(board[point.x][i] == 0)
addedPoints.add(new Point(point.x, i));
}
return addedPoints;
}
static Set<Point> seeLeftward(Point point){
Set<Point> addedPoints = new HashSet<>();
for(int i = point.y-1; i >= 0; i--){
if(board[point.x][i] == 6)
break;
if(board[point.x][i] == 0)
addedPoints.add(new Point(point.x, i));
}
return addedPoints;
}
static void markPoints(Set<Point> points){
for (Point point : points) {
board[point.x][point.y] = -1;
}
}
static void revertPoints(Set<Point> points){
for (Point point : points) {
board[point.x][point.y] = 0;
}
}
static int countHiddenPoints(){
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(board[i][j] ==0) {
count++;
}
}
}
return count;
}
static class CCTV{
Point point;
int type;
public CCTV(Point point, int type){
this.point = point;
this.type = type;
}
}
static class Point{
int x,y;
public Point(int x, int y){
this.x=x;
this.y=y;
}
}
}