백준 15683번 감시 :: 마이구미

이 글은 백준 알고리즘 문제 15683번 "감시" 를 풀이한다.

2018 삼성 SW 역량 테스트 문제이다.

접근 방법은 브루트포스와 DFS 를 통해 풀이한다.

문제 링크 - https://www.acmicpc.net/problem/15683

DFS - http://mygumi.tistory.com/102

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

1번	2번	3번	4번	5번

1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.

CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.

CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.

---

문제 해결을 위해서는 모든 경우를 전부 확인하면 되는 문제이다.

문제는 크게 어렵지 않지만, 구현이 단순하지는 않는 문제이다. 

항상 이런 유형을 내고 있는 것으로 보인다.

문제는 크게 다음과 같다.

1. 총 5개의 CCTV 가 존재하는데, 각 CCTV 는 감시할 수 있는 방향이 다르다.
2. CCTV 는 90도 회전이 가능하다.
3. CCTV 는 벽을 통과할 수 없지만, CCTV 는 통과할 수 있다.

2번이 의미하는 것은 다음과 같다.

위와 같은 형태로 90도 회전을 하기 때문에 1번은 단순히 오른쪽 방향만 감시하는 것이 아니다.

결과적으로는 다음과 같이 감시할 수 있다.

• 1번 CCTV - (오른쪽), (위쪽), (왼쪽), (아래쪽) => 4가지
• 2번 CCTV - (왼쪽, 오른쪽), (위쪽, 아래쪽) => 2가지
• 3번 CCTV - (위쪽, 오른쪽), (오른쪽, 아래쪽), (아래쪽, 왼쪽), (왼쪽, 위쪽) => 4가지
• 4번 CCTV - (왼쪽, 위쪽, 오른쪽), (위쪽, 오른쪽, 아래쪽), (오른쪽, 아래쪽, 왼쪽), (아래쪽, 왼쪽, 위쪽) => 4가지
• 5번 CCTV - (왼쪽, 위쪽, 오른쪽, 아래쪽) => 1가지

위의 모든 경우를 위해 DFS 와 같이 재귀적으로 모든 경우를 탐색한다.

public static void search(int cctvIndex, int[][] prev) {
    int[][] visited = new int[n][m];
    if (cctvIndex == list.size()) {
        // 모든 CCTV 탐색했을 경우
        // 사각지대 갯수 카운트
    } else {
        ...........
        switch (idx) {
            case 1:
                for (int k = 0; k < 4; k++) {
                    for (int i = 0; i < n; i++) {
                        // 이전 감시 현황 가져옴
                        visited[i] = Arrays.copyOf(prev[i], m);
                    }
                    detect(visited, y, x, k); // 감시여부 체크
                    search(cctvIndex + 1, visited); // 다음 CCTV 탐색
                }
                break;
            case 2:
            case 3:
            case 4:
            case 5:
        }
    }
}

위 코드가 실질적인 코드이다.

1. 이전 감시 현황(prev)을 가져온다.

2. CCTV 감시한다.

3. 다음 CCTV 를 탐색한다.

* 각 경우에서 감시된 현황을 위해 매번 탐색할 때마다 깊은 복사를 사용한다. (prev -> visited)

Github - https://github.com/hotehrud/acmicpc/blob/master/SAMSUMG/15683.java

static int n, m, ans = Integer.MAX_VALUE;
static int[][] map;
static ArrayList<Node> list = new ArrayList<Node>();
 
private void solve() {
    n = sc.nextInt();
    m = sc.nextInt();
    map = new int[n][m];
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int v = sc.nextInt();
            map[i][j] = v;
            if (1 <= v && v <= 5) {
                list.add(new Node(i, j, v));
            }
        }
    }
    search(0, map);
    System.out.println(ans);
}
 
public static void search(int cctvIndex, int[][] prev) {
    int[][] visited = new int[n][m];
    if (cctvIndex == list.size()) {
        int temp = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (prev[i][j] == 0) {
                    temp++;
                }
            }
        }
        if (temp < ans) {
            ans = temp;
        }
    } else {
        Node node = list.get(cctvIndex);
        int idx = node.idx;
        int x = node.x;
        int y = node.y;
 
        switch (idx) {
            case 1:
                for (int k = 0; k < 4; k++) {
                    for (int i = 0; i < n; i++) {
                        visited[i] = Arrays.copyOf(prev[i], m);
                    }
                    detect(visited, y, x, k);
                    search(cctvIndex + 1, visited);
                }
                break;
            case 2:
                for (int k = 0; k < 2; k++) {
                    for (int i = 0; i < n; i++) {
                        visited[i] = Arrays.copyOf(prev[i], m);
                    }
                    detect(visited, y, x, k);
                    detect(visited, y, x, k + 2);
                    search(cctvIndex + 1, visited);
                }
                break;
            case 3:
                for (int k = 0; k < 4; k++) {
                    for (int i = 0; i < n; i++) {
                        visited[i] = Arrays.copyOf(prev[i], m);
                    }
                    detect(visited, y, x, k);
                    detect(visited, y, x, (k + 1) % 4);
                    search(cctvIndex + 1, visited);
                }
                break;
            case 4:
                for (int k = 0; k < 4; k++) {
                    for (int i = 0; i < n; i++) {
                        visited[i] = Arrays.copyOf(prev[i], m);
                    }
                    detect(visited, y, x, k);
                    detect(visited, y, x, (k + 1) % 4);
                    detect(visited, y, x, (k + 2) % 4);
                    search(cctvIndex + 1, visited);
                }
                break;
            case 5:
                for (int i = 0; i < n; i++) {
                    visited[i] = Arrays.copyOf(prev[i], m);
                }
                detect(visited, y, x, 0);
                detect(visited, y, x, 1);
                detect(visited, y, x, 2);
                detect(visited, y, x, 3);
                search(cctvIndex + 1, visited);
                break;
        }
    }
}
 
public static void detect(int[][] visited, int i, int j, int direction) {
    switch (direction) {
        case 0:
            for (int k = j; k >= 0; k--) {
                if (map[i][k] == 6) {
                    break;
                }
                visited[i][k] = 7;
            }
            break;
        case 1:
            for (int k = i; k >= 0; k--) {
                if (map[k][j] == 6) {
                    break;
                }
                visited[k][j] = 7;
            }
            break;
        case 2:
            for (int k = j; k < m; k++) {
                if (map[i][k] == 6) {
                    break;
                }
                visited[i][k] = 7;
            }
            break;
        case 3:
            for (int k = i; k < n; k++) {
                if (map[k][j] == 6) {
                    break;
                }
                visited[k][j] = 7;
            }
            break;
    }
}
 
public static class Node {
    int x;
    int y;
    int idx;
 
    Node(int y, int x, int idx) {
        this.x = x;
        this.y = y;
        this.idx = idx;
    }
}