[백준]JAVA - 15683번: 감시

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

15683번: 감시

풀이

5가지의 감시 카메라가 상우하좌로 돌면서 사각지대의 최솟값을 찾아야한다.

감시 카메라의 경우의 수는 아래와 같다.

1번 카메라: 4가지

2번 카메라: 2가지

3번 카메라: 4가지

4번 카메라: 4가지

5번 카메라: 1가지

 

예를 들어 1번과 2번 카메라가 하나씩 존재한다면 경우의 수는 4 x 2 = 8가지이다. 경우의 수를 다 돌려주기 위해서 완전탐색 dfs를 돌려준다.

public static void dfs(int cnt) {
    if (cnt == cctv.size()) {
        setMap();
        return;
    }
		
    CCTV now = cctv.get(cnt);
		
    switch (now.level) {
    case 2:
        for (int i=0; i<4; i+=2) {
            dir[cnt] = i;
            dfs(cnt+1);
        }
        break;
			
    case 5:
        dir[cnt] = 0;
        dfs(cnt+1);
        break;
			
    default:
        for (int i=0; i<4; i++) {
            dir[cnt] = i;
            dfs(cnt+1);
        }
        break;
    }
}

2번 감시 카메라는 경우의 수가 2개이므로 반복문을 2번 돌려준다. 나머지도 경우의 수에 맞게 dfs를 반복해준다. dfs를 반복했을 때 초기 맵에 생성됐던 감시 카메라 개수와 같아지면 사각지대를 찾아준다.

 

// 0 위, 1 오, 2 아래, 3 왼
public static void setMap() {
    copyMap = new int[N][M];
    for (int i = 0; i < N; i++) {
        System.arraycopy(map[i], 0, copyMap[i], 0, M);
    }

    for (int i=0; i<cctv.size(); i++) {
        CCTV now = cctv.get(i);
			
        if (now.level == 1) {
            watch(now, dir[i]);
        } else if (now.level == 2) {
            if (dir[i] == 0) {
                watch(now, 0);
                watch(now, 2);
            } else {
                watch(now, 1);
                watch(now, 3);
            }
        } else if (now.level == 3) {
            if (dir[i] == 3) {
                watch(now, 0);
                watch(now, 3);
            } else {
                watch(now, dir[i]);
                watch(now, dir[i]+1);
            }
        } else if (now.level == 4) {
            if (dir[i] == 0) {
                watch(now, 0);
                watch(now, 1);
                watch(now, 2);
            }
            if (dir[i] == 1) {
                watch(now, 1);
                watch(now, 2);
                watch(now, 3);
            }
            if (dir[i] == 2) {
                watch(now, 0);
                watch(now, 2);
                watch(now, 3);
            }
            if (dir[i] == 3) {
                watch(now, 0);
                watch(now, 1);
                watch(now, 3);
            }
        } else if (now.level == 5) {
            watch(now, 0);
            watch(now, 1);
            watch(now, 2);
            watch(now, 3);
        }
    }
		
    count();
}

완전탐색 dfs를 돌면서 입력해준 방향 배열 (dir[cnt])의 값에 따라서 감시 카메라의 방향을 잡고 사각지대를 찾아준다.

 

public static void watch(CCTV cctv, int d) {
    int nx = cctv.x + dx[d];
    int ny = cctv.y + dy[d];
		
    while(nx >= 0 && nx < N && ny >= 0 && ny < M && copyMap[nx][ny] != 6) {
        copyMap[nx][ny] = cctv.level;

        nx += dx[d];
        ny += dy[d];
    }
}

카메라의 번호와 방향이 정해졌다면 해당 방향으로 벽이 나오거나 맵을 벗어나지 않을 때까지 값을 변경해주면 된다. 감시카메라가 비추지 않는 곳은 0으로 정의되어있기 때문에 0부터 6이 아닌 임의의 수로 변경하면 된다.

 

값을 변경해줄 때 주의할 점은 초기의 맵을 복사해서 사용하는 것이다. 초기의 맵을 사용한다면 이미 값이 변해버렸기 때문에 제대로 된 탐색이 어려울 수 있다.

 

<최종코드>

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

public class Main {
    static int N, M;
    static int[][] map, copyMap;
    static ArrayList<CCTV> cctv;
    static int[] dx = {-1, 0 , 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int[] dir;
    static int min = 500;
	
    public static class CCTV {
        int x;
        int y;
        int level;
		
        public CCTV (int x, int y, int level) {
            this.x = x;
            this.y = y;
            this.level = level;
        }
    }
	
    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());
		
        map = new int[N][M];
        cctv = new ArrayList<>();
		
        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 (0 < map[i][j] && map[i][j] < 6) {
                    cctv.add(new CCTV(i, j, map[i][j]));
                }
            }
        }
        dir = new int[cctv.size()];
        dfs(0);
		 
        System.out.println(min);
    }
	
    public static void dfs(int cnt) {
        if (cnt == cctv.size()) {
            setMap();
            return;
        }
		
        CCTV now = cctv.get(cnt);
		
        switch (now.level) {
        case 2:
            for (int i=0; i<4; i+=2) {
                dir[cnt] = i;
                dfs(cnt+1);
            }
            break;
			
        case 5:
            dir[cnt] = 0;
            dfs(cnt+1);
            break;
			
        default:
            for (int i=0; i<4; i++) {
                dir[cnt] = i;
                dfs(cnt+1);
            }
            break;
        }
    }
	
    // 0 위, 1 오, 2 아래, 3 왼
    public static void setMap() {
        copyMap = new int[N][M];
        for (int i = 0; i < N; i++) {
            System.arraycopy(map[i], 0, copyMap[i], 0, M);
        }

        for (int i=0; i<cctv.size(); i++) {
            CCTV now = cctv.get(i);
			
            if (now.level == 1) {
                watch(now, dir[i]);
            } else if (now.level == 2) {
                if (dir[i] == 0) {
                    watch(now, 0);
                    watch(now, 2);
                } else {
                    watch(now, 1);
                    watch(now, 3);
                }
            } else if (now.level == 3) {
                if (dir[i] == 3) {
                    watch(now, 0);
                    watch(now, 3);
                } else {
                    watch(now, dir[i]);
                    watch(now, dir[i]+1);
                }
            } else if (now.level == 4) {
                if (dir[i] == 0) {
                    watch(now, 0);
                    watch(now, 1);
                    watch(now, 2);
                }
                if (dir[i] == 1) {
                    watch(now, 1);
                    watch(now, 2);
                    watch(now, 3);
                }
                if (dir[i] == 2) {
                    watch(now, 0);
                    watch(now, 2);
                    watch(now, 3);
                }
                if (dir[i] == 3) {
                    watch(now, 0);
                    watch(now, 1);
                    watch(now, 3);
                }
            } else if (now.level == 5) {
                watch(now, 0);
                watch(now, 1);
                watch(now, 2);
                watch(now, 3);
            }
        }
		
        count();
    }
	
    public static void watch(CCTV cctv, int d) {
        int nx = cctv.x + dx[d];
        int ny = cctv.y + dy[d];
		
        while(nx >= 0 && nx < N && ny >= 0 && ny < M && copyMap[nx][ny] != 6) {
            copyMap[nx][ny] = cctv.level;

            nx += dx[d];
            ny += dy[d];
        }
    }
	
    public static void count() {
        int cnt = 0;
		
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                if (copyMap[i][j] == 0) {
                    cnt++;
                }
            }
        }
		
        min = Math.min(min, cnt);
    }
}

내가 생각한 시간 복잡도: CCTV의 최대 개수는 8개, CCTV 한 개의 최대 회전수는 4방향으로 $4^{8}$, CCTV의 감시 범위를 확인하는데 4NM이므로 O($4^{8}$ x 4NM)