백준 1236번 성 지키기 :: 마이구미

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

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

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

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

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

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

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

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

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

예를 들면 다음과 같다.

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

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

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

결국 모든 각 행, 열에는 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

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);
}