• 백준 15683번 감시 :: 마이구미
    알고리즘 풀이/브루트 포스 2018. 4. 28. 18:15
    반응형

    이 글은 백준 알고리즘 문제 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번이 의미하는 것은 다음과 같다.


    15683번 감시15683번 감시


    위와 같은 형태로 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


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    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 (<= 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;
        }
    }
    cs


    반응형

    댓글 8

    • Favicon of https://mygumi.tistory.com 마이구미 mygumi 2019.09.17 23:06 신고

      Ko William DJ - 아 이 문제는 그닥 어렵진 않은데 문제 자체를 이해하는데 오래걸렸네용 ㅋ 항상 감사합니다 젤리님 ♥
      => 2018 삼성 문제를 풀고 계시군요 ㅎ
      말씀하신대로 문제 자체를 이해하는데 오래 걸리는 문제밖에 없었죠!
      도움이 되셨다니 감사합니다~

    • Favicon of https://mygumi.tistory.com 마이구미 mygumi 2019.09.17 23:06 신고

      함함 - 마이구미님 detect에서 씨씨티비 감시 방향을 볼 때 direction 0이 서쪽, 1이 북쪽, 2가 동쪽, 3이 남쪽 맞나요? 감사합니다!
      => 감사합니다~
      그건 크게 중요하진 않습니다.
      제가 판단하기에는 좀 그렇지만...?
      남겨주신 댓글들을 보아할 때, "아 이렇게 할 수 있구나?" 보다는 지금 이해하시는 단계보다 조금 더 깊게 더 시간을 가지고 보시면 더욱 좋으시지 않을까? 생각합니다! (한가지 예로는 글을 보고 방법을 알았으니 아무것도 안보고 다시 문제를 해결해보는?)

    • Favicon of https://ju-nam2.tistory.com 주남2 2019.10.15 21:14 신고

      어떻게 해야겠다는 생각이 났는데 완전탐색을 어떻게 해야하나 고민을 하다가 들어왔네요 ㅠㅠ 평소에 순열, 조합을 외워서 경우의 수를 하다가 순열 조합을 못쓰게 되니 어쩔줄을 모르네요..ㅠㅠ 재귀에 대한 이해를 잘 하고 싶은데 방법이 있을까요?? 항상 잘보고 있습니다 감사합니다 ㅎㅎ

      • Favicon of https://mygumi.tistory.com 마이구미 mygumi 2019.10.15 23:26 신고

        DFS 코드를 우선 이해하는 게 쉽지 않을까합니다.
        재귀적으로 동작하는 코드는 손으로 그려가면서 확실히 이해하고 넘어가야할듯합니다...
        도움을 크게 못드리는것 같군요...

    • 123 2019.11.12 19:33

      안녕하세요! 좋은글 감사합니다. -치치-

    • Favicon of https://byeongyeon.tistory.com whyWhale 2021.02.01 17:34 신고

      dfs에서 중간 결과 테이블을 넘겨야 하는지 전혀 생각이 안났는데... 꺠닫고 갑니당....

Designed by Tistory.