BOJ - 감시 15683번 (Java)

❓ 문제 - 백준 감시 15683번 - JAVA 풀이법

출처 

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

 

 

📝 문제해결법

1. 이 문제는 DFS+구현으로 풀었다.

• 각 CCTV의 타입을 받아서 각 타입에 맞춰서 회전된 상태를 조합하여 사각지대의 최소값을 찾는다.
• dx, dy로 방향 북(0), 남(1), 서(2), 동(3)으로 이동할 수 있도록 구현한다.
• CCTV 타입이 1인 경우 90도 회전할 수 있는 경우는 북(0) / 남(1) / 서(2) / 동(3)  4가지 경우이다.
• CCTV 타입이 2인 경우 90도 회전할 수 있는 경우는 서(2), 동(3) / 북(0), 남(1) 2가지 경우이다.
• CCTV 타입이 3인 경우 90도로 회전할 수 있는 경우는 북(0), 동(3) / 남(1), 3(동) / 남(1), 서(2) / 북(0), 서(2) 4가지 경우이다.
• CCTV 타입이 4인 경우는 90도로 회전할 수 있는 경우는 북(0), 서(2), 동(3) / 북(0), 남(1), 동(3) / 남(1), 서(2), 동(3) / 북(0), 남(1), 서(2) 4가지 경우이다.
• CCTV 타입이 5인 경우는 북(0), 남(1), 서(2), 동(3) 1가지 경우이다.
• 각 CCTV의 있는 위치 x, y, type을 cctv list에 넣어준다. 그 후 dfs(조합)으로 각 cctv마다 특정 경우에 조합으로 감시를 했을 때 사각지대가 얼마인지 구한 후 최솟값을 갱신한다. 
• 사각지대를 구할 때는 check() 함수를 활용한다.

 

💻 소스코드

// BOJ - 감시 (15683번)
// DFS(조합)

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

public class Main_15683 {
	
	public static int[] dx = {-1, 1, 0, 0};
	public static int[] dy = {0, 0, -1, 1};
	
	public static int[][][] mode = {{{0}}, {{0}, {1}, {2}, {3}}, {{2, 3}, {0, 1}},
			{{0, 3}, {1, 3}, {1, 2}, {0, 2}},
			{{0, 2, 3}, {0, 1, 3}, {1, 2, 3}, {0, 1, 2}},
			{{0, 1, 2, 3}}};
	public static ArrayList<Node> cctv;
	public static class Node {
		int x;
		int y;
		int type;
		public Node(int x, int y, int type) {
			this.x= x;
			this.y= y;
			this.type = type;
		}
	}
	public static int n, m, ans;
	public static int[][] map;	
	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());
		cctv = new ArrayList<>();
		int zero_cnt = 0;
		int[][] map = new int[n][m];
		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] >= 1 && map[i][j] <= 5){
					cctv.add(new Node(i, j, map[i][j]));
				} else if(map[i][j] == 0) zero_cnt++;
			}
		}
		ans = zero_cnt;
		combination(0, cctv.size(), map);
		System.out.println(ans);
	}
	
	
	public static void combination(int depth, int r, int[][] map) {
		if(depth == r) {
			int cnt = check(map);
			ans = Math.min(ans, cnt);
			return;
		}
		int cctv_type = cctv.get(depth).type;
		int x = cctv.get(depth).x;
		int y = cctv.get(depth).y;
		
		
		for(int i=0;i<mode[cctv_type].length;i++) {
			int[][] map_copy = new int[n][m];
			for(int k=0;k<n;k++) {
				map_copy[k] = map[k].clone();
			}
			
			for(int j=0;j<mode[cctv_type][i].length;j++){
				int dir = mode[cctv_type][i][j];
		
				int nx = x + dx[dir];
				int ny = y + dy[dir];
				while (true) {
					if(nx < 0 || nx >= n || ny < 0 || ny >= m) {
						break;
					}
					
					if(map[nx][ny] == 6) {
						break;
					}
					map_copy[nx][ny] = -1;
					nx += dx[dir];
					ny += dy[dir];
				}
			}

			
			combination(depth+1, r, map_copy);
		}
	}
	
	public static int check(int[][] map) {
		int cnt = 0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(map[i][j] == 0) {
					cnt++;
				}
			}
		}
		return cnt;
	}
	
	
	

}