BOJ 15683번: 감시

문제

문제 바로가기> BOJ 15683번: 감시

15683번: 감시

 

풀이

cctv의 개수가 최대 8개로 적은 편이다.

따라서 가능한 cctv 방향을 모두 시뮬레이션 해보면서, 브루트포스 방식으로 문제를 풀었다.

탐색 방향을 미리 `dir` 배열에 정해두고, 모든 cctv의 방향을 정했을 때, 시뮬레이션 해주면 된다.

 

C++

#include<iostream>
#include<vector>
#define EMPTY 0
#define WALL 6
#define MAX 10
using namespace std;

struct CCTV{int y, x, num;};
vector<CCTV> cctv;

int N, M, ans = MAX*MAX;
int dy[] = {0, 1, 0, -1};  // → ↓ ← ↑
int dx[] = {1, 0, -1, 0};
int dir[MAX], map[MAX][MAX], copy_map[MAX][MAX];

void input(){
    cin >> N >> M;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin >> map[i][j];
            if(0<map[i][j] && map[i][j]<6) cctv.push_back({i, j, map[i][j]}); // cctv 위치, 종류 저장
        }
    }
}

void check_area(int y, int x, int d){
    int ny=y, nx=x;
    while(1){
        if(ny<0 || ny>=N || nx<0 || nx>=M || map[ny][nx]==WALL) return; // 범위를 벗어나는 경우, 벽인 경우
        copy_map[ny][nx] = map[y][x]; // 감시 영역 check
        ny+=dy[d]; nx+=dx[d]; // move
    }
}

int get_blind_spot(){
    
    // copy 
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++) copy_map[i][j] = map[i][j];
    }

    // check surveillance area
    for(int i=0; i<cctv.size(); i++){ // cctv 종류에 따라 감시 영역 체크
        int num = cctv[i].num;
        int y = cctv[i].y, x = cctv[i].x;
        if(num == 1) check_area(y, x, dir[i]);
        else if(num == 2){
            check_area(y, x, dir[i]);
            check_area(y, x, (dir[i]+2)%4);
        }
        else if(num == 3){
            check_area(y, x, dir[i]);
            check_area(y, x, (dir[i]+1)%4);
        }
        else if(num == 4){
            check_area(y, x, dir[i]);
            check_area(y, x, (dir[i]+1)%4);
            check_area(y, x, (dir[i]+2)%4);
        }
        else{
            check_area(y, x, dir[i]);
            check_area(y, x, (dir[i]+1)%4);
            check_area(y, x, (dir[i]+2)%4);
            check_area(y, x, (dir[i]+3)%4);
        }
    }

    // check blind spot
    int blind_spot = 0;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(copy_map[i][j] == EMPTY) blind_spot++;
        }
    } return blind_spot;
}

void solution(int cnt){
    if(cnt == cctv.size()){
        ans = min(ans, get_blind_spot());
        return;
    }
    for(int i=0; i<4; i++){
        dir[cnt] = i; // cctv 방향 설정
        solution(cnt+1);
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    solution(0);
    cout << ans;
}

 

Java

import java.io.*;
import java.util.*;

public class Main{
	
	static final int EMPYT = 0;
	static final int WALL = 6;
	static final int MAX = 8; // CCTV의 최대 개수는 8개를 넘지 않음
	
	static final int dy[] = {0, 1, 0, -1}; // 우 하 좌 상
	static final int dx[] = {1, 0, -1, 0};
	
	
	static int N, M, emptycnt=0;
	static int ans = Integer.MAX_VALUE;	
	static int[][] map;
	static boolean[][] visited;
	static int[] dir;
	static List<int[]> cctv = new ArrayList<>();
	
	public static void main(String[] args) throws Exception {
		// System.setIn(new FileInputStream("res/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st =new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		dir = new int[MAX];
		
		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]==EMPYT) emptycnt++;
				else if(map[i][j]!=WALL) cctv.add(new int[] {i,j});
			}
		}
		solution(0);
		System.out.println(ans);
	}

	static void solution(int cnt) {
		if(cnt == cctv.size()) {
			ans = Math.min(ans, get_blind_spot());
			return ; 
		}
		for(int d=0; d<4; d++) {
			dir[cnt] = d;
			solution(cnt+1);
		}
	}

	static int get_blind_spot() { // 사각 지대의 크기 반환
		
		int cnt = 0;
		visited = new boolean[N][M];
		
		for(int n=0; n<cctv.size(); n++) {
			int y = cctv.get(n)[0];
			int x = cctv.get(n)[1];
			int d = dir[n];
			
			if(map[y][x] == 1) cnt+=check(y, x, d);
			else if(map[y][x] == 2) {
				cnt+=check(y, x, d);
				cnt+=check(y, x, (d+2)%4);	
			}
			else if(map[y][x] == 3) {
				cnt+=check(y, x, d);
				cnt+=check(y, x, (d+1)%4);
			}
			else if(map[y][x] == 4) {
				cnt+=check(y, x, d);
				cnt+=check(y, x, (d+2)%4);
				cnt+=check(y, x, (d+3)%4);
			}
			else if(map[y][x] == 5) {
				cnt+=check(y, x, d);
				cnt+=check(y, x, (d+1)%4);
				cnt+=check(y, x, (d+2)%4);
				cnt+=check(y, x, (d+3)%4);
			}
		}
		return emptycnt-cnt;
	}

	static int check(int y, int x, int d) {
		
		int ny = y;
		int nx = x;
		int cnt = 0;
		while(true){
			ny+=dy[d]; nx+=dx[d];
			if(ny<0 || ny>=N || nx<0 || nx>=M || map[ny][nx]==WALL) break; // 범위를 벗어나는 경우 벽인 경우 
			if(map[ny][nx] == EMPYT && !visited[ny][nx]) {
				cnt++;
				visited[ny][nx] = true;
			}
		}
		return cnt;
	}
}