Java

[백준 15683] 감시 (JAVA)

iheeeee6-6 2023. 4. 5. 21:20
728x90

https://www.acmicpc.net/problem/15683

 

15683번: 감시

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감

www.acmicpc.net

전체적인 배열 1

사각지대 현황 배열 1

cctv 위치 리스트 1

 

dfs로 모든 cctv의 각도에 따른 사각지대를 확인한 후 최소값을 출력한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

	static int result=Integer.MAX_VALUE;
	static int N, M;

	static class Dot {
		int x;
		int y;
		int num;

		Dot(int x, int y, int num) {
			this.x = x;
			this.y = y;
			this.num = num;
		}
	}

	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());
		int[][] arr = new int[N][M];
		ArrayList<Dot> cctvList = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				if (arr[i][j] > 0 && arr[i][j] != 6) {
					cctvList.add(new Dot(i, j, arr[i][j]));
				}
			}
		}

		check(0, arr, cctvList);
		System.out.println(result);

	}

	static void check(int cnt, int[][] arr, ArrayList<Dot> cctvList) {
		if (cnt == cctvList.size()) {
			result = Math.min(result, CountZero(arr));
			return;
		}
		
		int cctvNum = cctvList.get(cnt).num;
		int x = cctvList.get(cnt).x;
		int y = cctvList.get(cnt).y;
		
		int[][] tmp;
		if(cctvNum==1) {
			tmp=copyMap(arr);
			checkLeft(tmp,x,y);
			check(cnt+1,tmp,cctvList);
			
			tmp = copyMap(arr);
			checkRight(tmp,x,y);
			check(cnt+1,tmp,cctvList);
			
			tmp = copyMap(arr);
			checkDown(tmp,x,y);
			check(cnt+1,tmp,cctvList);
			
			tmp = copyMap(arr);
			checkUp(tmp,x,y);
			check(cnt+1,tmp,cctvList);
			
		}else if(cctvNum==2) {
			tmp=copyMap(arr);
			checkLeft(tmp,x,y);
			checkRight(tmp,x,y);
			check(cnt+1,tmp,cctvList);

			tmp=copyMap(arr);
			checkUp(tmp,x,y);
			checkDown(tmp,x,y);
			check(cnt+1,tmp,cctvList);
		}else if(cctvNum==3) {
			tmp=copyMap(arr);
			checkUp(tmp,x,y);
			checkRight(tmp,x,y);
			check(cnt+1,tmp,cctvList);

			tmp=copyMap(arr);
			checkDown(tmp,x,y);
			checkRight(tmp,x,y);
			check(cnt+1,tmp,cctvList);

			tmp=copyMap(arr);
			checkDown(tmp,x,y);
			checkLeft(tmp,x,y);
			check(cnt+1,tmp,cctvList);

			tmp=copyMap(arr);
			checkUp(tmp,x,y);
			checkLeft(tmp,x,y);
			check(cnt+1,tmp,cctvList);
		}else if(cctvNum==4) {
			tmp=copyMap(arr);
			checkUp(tmp,x,y);
			checkRight(tmp,x,y);
			checkLeft(tmp,x,y);
			check(cnt+1,tmp,cctvList);

			tmp=copyMap(arr);
			checkUp(tmp,x,y);
			checkRight(tmp,x,y);
			checkDown(tmp,x,y);
			check(cnt+1,tmp,cctvList);

			tmp=copyMap(arr);
			checkDown(tmp,x,y);
			checkLeft(tmp,x,y);
			checkRight(tmp,x,y);
			check(cnt+1,tmp,cctvList);

			tmp=copyMap(arr);
			checkUp(tmp,x,y);
			checkLeft(tmp,x,y);
			checkDown(tmp,x,y);
			check(cnt+1,tmp,cctvList);
		} 
		else {
			tmp=copyMap(arr);
			checkUp(tmp,x,y);
			checkLeft(tmp,x,y);
			checkRight(tmp,x,y);
			checkDown(tmp,x,y);
			check(cnt+1,tmp,cctvList);
		}
	}

	static void checkLeft(int[][] arr, int x,int y) {
		for(int i=y-1;i>=0;i--) {
			if(arr[x][i]==6) return;
			if(arr[x][i]!=0) continue;
			arr[x][i]=-1;
		}
	}
	

	static void checkRight(int[][] arr, int x,int y) {
		for(int i=y+1;i<M;i++) {
			if(arr[x][i]==6) return;
			if(arr[x][i]!=0) continue;
			arr[x][i]=-1;
		}
	}
	
	static void checkUp(int[][] arr, int x,int y) {
		for(int i=x-1;i>=0;i--) {
			if(arr[i][y]==6) return;
			if(arr[i][y]!=0) continue;
			arr[i][y]=-1;
		}
	}
	
	static void checkDown(int[][] arr, int x,int y) {
		for(int i=x+1;i<N;i++) {
			if(arr[i][y]==6) return;
			if(arr[i][y]!=0) continue;
			arr[i][y]=-1;
		}
	}
	
	static int CountZero(int[][] arr) {
		int count = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (arr[i][j] == 0)
					count++;
			}
		}
		return count;
	}

	static int[][] copyMap(int[][] arr) {
		int[][] tmp = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				tmp[i][j] = arr[i][j];
			}
		}
		return tmp;
	}

}

'Java' 카테고리의 다른 글

[백준 1717] 집합의 표현 (JAVA)  (0) 2023.04.11
[백준 21608] 상어 초등학교 (JAVA)  (0) 2023.04.05
[백준 16235] 나무 재테크 (JAVA)  (0) 2023.04.05
[백준 9466] 텀 프로젝트 (JAVA)  (0) 2023.04.03
[백준 1107] 리모컨 (JAVA)  (0) 2023.03.29