[Java] 백준 / 감시 / 15683번

[Java] 백준 / 감시 / 15683번

문제

감시 문제 링크

접근 방식

문제를 보면 Cctv의 방향을 바꿔가며 최소의 사각지대 수를 찾아 출력해야 하기 때문에 방향을 중복순열로 구하고 해당 방향에 맞게 Cctv의 감시영역을 #으로 채우고 사각지대 값을 구해가며 최솟값을 찾는 방식이 떠올랐다

1. 4방향 (위 오른쪽 아래 왼쪽)을 가리킬 deltas 배열을 만들고 이를 접근할 인덱스를 cctv 수만큼 중복순열로 구한다
2. cctv 방향 배열을 만들면 이를 가지고 각 cctv 번호에 맞게 #을 칠한 후 사각지대 최솟값을 구한다

코드

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_15683_정현명 {

	static int N,M;
	static int mat[][];
	static List<Cctv> cctvs;
	static int deltaIdx[];
	static int[][] deltas = {{-1,0},{0,1},{1,0},{0,-1}};
	static int minBlindSpot;
	
	// Cctv 클래스 ( 행과 열을 가짐 )
	public static class Cctv{
		int r;
		int c;
		
		Cctv(int r, int c){
			super();
			this.r = r;
			this.c = c;
		}
	}
		
	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()); // 열
		
		mat = new int[N][M]; // 사무실 각 칸 정보
		cctvs = new ArrayList<>(); // Cctv 객체 배열
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<M;j++) {
				mat[i][j] = Integer.parseInt(st.nextToken());
				if(mat[i][j] <=5 && mat[i][j] >=1) cctvs.add(new Cctv(i,j));
			}
		}
		
		// ================== 솔루션 ==================
		
		deltaIdx = new int[cctvs.size()]; // cctv 순으로 방향을 가지는 배열
		minBlindSpot = N * M; // 사각지대 최솟값
		perRep(0); // 중복순열함수 실행
		
		
		// ================== 출력 ===================
		System.out.println(minBlindSpot);
	}
	
	
	// cctv 방향으로 중복순열을 만드는 함수
	public static void perRep(int cnt) {
		// 모든 cctv의 방향이 결정되면 사각지대를 찾는 함수 호출
		if(cnt == cctvs.size()) {
			searchBlindSpot();
			return;
		}
		
		for(int i=0;i<4;i++) {
			deltaIdx[cnt] = i;
			perRep(cnt+1);
		}
	}
	
	// 사각지대를 찾는 함수
	public static void searchBlindSpot() {
		
		// 사무실 각 칸 깊은 복사
		int tempMat[][] = new int[N][M];
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				tempMat[i][j] = mat[i][j];
			}
		}
		
		
		// 각 cctv에 대해 만들어 놓은 중복 순열 방향으로 Cctv 번호에 맞게 칸을 채움
		for(int i=0;i<cctvs.size();i++) {
			Cctv cctv = cctvs.get(i);
			int way = deltaIdx[i];
			
			switch(tempMat[cctv.r][cctv.c]) {
			
			case 1:
				tempMat = fillPound(way, tempMat, cctv.r, cctv.c);
				break;
			
			case 2:
				tempMat = fillPound(way, tempMat, cctv.r, cctv.c);
				tempMat = fillPound((way+2)%4, tempMat, cctv.r, cctv.c);
				break;
			
			case 3:
				tempMat = fillPound(way, tempMat, cctv.r, cctv.c);
				tempMat = fillPound((way+1)%4, tempMat, cctv.r, cctv.c);
				break;
				
				
			case 4 :
				tempMat = fillPound(way, tempMat, cctv.r, cctv.c);
				tempMat = fillPound((way+1)%4, tempMat, cctv.r, cctv.c);
				tempMat = fillPound((way+2)%4, tempMat, cctv.r, cctv.c);
				break;
				
			case 5 :
				tempMat = fillPound(0, tempMat, cctv.r, cctv.c);
				tempMat = fillPound(1, tempMat, cctv.r, cctv.c);
				tempMat = fillPound(2, tempMat, cctv.r, cctv.c);
				tempMat = fillPound(3, tempMat, cctv.r, cctv.c);
				break;
			}
		}
		
		countBlindSpot(tempMat); // 사각지대 횟수 카운팅
		
	}
	
	// 우물정자 #을 받아온 방향에 맞게 벽을 만나거나 사무실 밖으로 나가기 전까지 채움
	public static int[][] fillPound(int way, int[][] tempMat, int r, int c) {
		while(true) {
			r += deltas[way][0];
			c += deltas[way][1];
			if(r < 0 || r >= N || c < 0 || c >= M || tempMat[r][c] == 6)break;
			if(tempMat[r][c] != 0) continue; // 다른 Cctv를 만날 경우 넘어가기
			tempMat[r][c] = '#'; // 0을 #으로 채우기
		}
		
		return tempMat;
	}
	
	// 사각지대 횟수 카운팅 함수
	public static void countBlindSpot(int[][] tempMat) {
		int cnt = 0;
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(tempMat[i][j] == 0) cnt++;
			}
		}
		
		minBlindSpot = minBlindSpot < cnt ? minBlindSpot : cnt;
	}

}