• 백준 1236번 성 지키기 :: 마이구미
    알고리즘 풀이/수학 2018. 3. 6. 00:36
    반응형

    이 글은 백준 알고리즘 1236번 "성 지키기" 를 풀이한다.

    접근 방식은 단순 문제 이해를 통한 수학적 접근이다.

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


    식이는 직사각형 모양의 성을 가지고 있다. 성의 1층은 몇 명의 경비원에 의해서 보호되고 있다. 영식이는 모든 행과 모든 열에 한 명 이상의 경비원이 있으면 좋겠다고 생각했다.

    성의 크기와 경비원이 어디있는지 주어졌을 때, 몇 명의 경비원을 최소로 추가해야 영식이를 만족시키는지 구하는 프로그램을 작성하시오.


    본인은 행과 열을 기준으로 무언가를 한다고 했을 때, DFS 또는 BFS 를 생각한다.

    이 문제의 경우에도 그렇게 생각했다.

    하지만 N의 크기 때문에 다소 무리가 있어, 다른 접근을 생각했다.


    문제의 핵심은 모든 행과 모든 열에 한명 이상의 경비원이 존재해야한다.

    예를 들면 다음과 같다.


    1236번 성 지키기


    위의 경우는 모든 행, 열에 경비원이 존재하는 것을 뜻한다.


    1236번 성 지키기


    하지만 위의 경우에는 1, 2, 3, 4, 5열 and 1행에 경비원이 존재하는 것을 뜻한다.

    그렇기에 2, 3, 4, 5행에 대한 경비원 추가가 필요하다.


    1236번 성 지키기


    결국 모든 각 행, 열에는 X(경비원)가 필요하다.

    여기서 살펴보면, 하나의 X는 어느 곳에 있든 1개의 행, 1개의 열, 총 2개를 차지한다.

    예를 들어, (1, 1) 에 있던지 (1, 3) 있던지 결국 총 2개를 차지한다.


    모든 경비원 위치에 대한 행과 열을 지우고, 남은 행과 열을 통해 정답을 구할 수 있다.

    남은 행과 열의 수는 큰 수가 정답이 된다.

    그 이유는 언급했듯이, 총 2개만 차지하기 때문이다.

    예를 들어, 1, 2, 3행이 남았고, 1, 2열이 남았다고 가정했을 경우, (1, 1), (2, 2) 에 경비원을 배치했을 경우에 3행에 대한 경비원이 필요하기 때문이다.


    Github - https://github.com/hotehrud/acmicpc/blob/master/algorithm/math/1236.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
    private void solve() {
        int n = sc.nextInt();
        int m = sc.nextInt();
        char[][] map = new char[n][m];
        boolean[] row = new boolean[n];
        boolean[] col = new boolean[m];
        int c = 0;
        int r = 0;
     
        for (int i = 0; i < n; i++) {
            map[i] = sc.readLine().toCharArray();
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 'X') {
                    col[j] = true;
                    row[i] = true;
                }
            }
        }
     
        for (int i = 0; i < n; i++) {
            if (!row[i]) {
                ++r;
            }
        }
     
        for (int i = 0; i < m; i++) {
            if (!col[i]) {
                ++c;
            }
        }
        System.out.println(c > r ? c : r);
    }
    cs
    반응형

    댓글 0

Designed by Tistory.