[백준]BOJ #11014: 컨닝 2

작성일 | In

문제 출처: https://www.acmicpc.net/problem/11014

문제

최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한다.

시험은 N행, M열 크기의 직사각형 교실에서 이루어진다. 교실은 1×1 크기의 단위 정사각형으로 이루어져 있는데, 각 단위 정사각형은 자리 하나를 의미한다.

최백준은 컨닝을 방지하기 위해서 다음과 같은 전략을 세웠다. 모든 학생은 자신의 왼쪽, 오른쪽, 왼쪽 대각선 위, 오른쪽 대각선 위, 이렇게 총 네 자리에 앉아있는 친구의 답지를 항상 베낀다고 가정한다. 따라서, 자리 배치는 모든 학생이 컨닝을 할 수 없도록 배치되어야 한다.

img

위의 그림을 보자. A, C, D 혹은 E에 다른 학생을 앉히는 것은 좋은 생각이 아니다. 그 이유는 이미 앉아있는 학생이 그들의 답안지를 베낄 우려가 있기 때문이다. 하지만, B에 다른 학생을 앉힌다면, 두 학생은 서로의 답지를 베낄 수 없어 컨닝의 우려가 없다.

위와 같이 컨닝이 불가능하도록 자리를 배치 하려는 최백준의 행동에 분노한 일부 학생들이 교실의 책상을 부셔버렸기 때문에, 일부 자리에는 학생이 앉을 수 없다.

최백준은 교실의 모양이 주어졌을 때, 이 곳에서 아무도 컨닝을 할 수 없도록 학생을 배치하였을 경우에 교실에 배치할 수 있는 최대 학생 수가 몇 명인지 궁금해졌다. 최백준을 위해 이를 구하는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트케이스의 개수 C가 주어진다. 각각의 테스트 케이스는 아래와 같이 두 부분으로 이루어진다.

첫 번째 부분에서는 교실의 세로길이 N과 가로길이 M이 한 줄에 주어진다. (1 ≤ M ≤ 80, 1 ≤ N ≤ 80)

두 번째 부분에서는 정확하게 N줄이 주어진다. 그리고 각 줄은 M개의 문자로 이루어져있다. 모든 문자는 ‘.’(앉을 수 있는 자리) 또는 ‘x’(앉을 수 없는 자리, 소문자)로 구성된다.

출력

각각의 테스트 케이스에 대해 그 교실에서 시험을 볼 수 있는 최대 학생의 수를 출력한다.

예제

입력 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
4
2 3
...
...
2 3
x.x
xxx
2 3
x.x
x.x
10 10
....x.....
..........
..........
..x.......
..........
x...x.x...
.........x
...x......
........x.
.x...x....
출력 1
1
2
3
4
4
1
2
46

풀이

N×M 의 자리들이 모두 정점들이라고 생각했을 때, 컨닝이 가능한 위치를 서로 인접한 정점이라고 볼 수 있다. 이 때 배치할 수 있는 최대 학생 수는 곧 서로 인접하지 않은 정점들을 최대로 선택하는 경우와 같다. 즉, 최대 독립 집합 (Maximum Independent Set) 을 구해야 함.

A graph may have many maximal independent sets (MIS) of widely varying sizes; the largest, or possibly several equally large, MISs of a graph is called a maximum independent set.

cf. )

img

Maximal Independent Set; 그래프에서 가능한 모든 최다 독립 집합. 위 모든 그림들이 해당함

Maximum Independent Set; Maximal Independent Set 중 정점 수가 가장 많은 경우 (4개).

**정리

In Bipartite graph G(V, E),

​ Maximum matching = Minimum vertex cover (Kőnig’s theorem)

​ Maximum Independent Set = V∖Minimum vertex cover

​ ∴ Maximum Independent Set = V∖Maximum matching

따라서 모든 정점 수에서 최대 매칭을 빼주면 최대 독립집합이 됨.

코드

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
int C;
int N, M;
char board[81][81];
int total_vertices=0;
vector<int> e[MAX];
int visited[MAX], rev[MAX];
int dr[6]={-1,0,1,-1,0,1};
int dc[6]={-1,-1,-1,1,1,1};

void init(){
    total_vertices=0;
    cin>>N>>M;
    foi(N){
        foj(M){
            cin>>board[i][j];
            if(board[i][j]=='.') total_vertices++;
        } 
    }
    foi(N*M) e[i].clear();    
    memset(rev, 0, sizeof(rev));
    // Indexing rule
    // num = M*(row-1) + column
}
int inBoard(int r, int c){
    if(r>0 && r<=N && c>0 && c<=M) return 1;
    else return 0;
}
inline int getIndex(int r, int c){
    return M*(r-1)+c;
}
int match(int v){
    for(int d:e[v]){
        if(visited[d]) continue;
        if(rev[d]){
            visited[d]=1;
            if(match(rev[d])){
                rev[d]=v;
                return 1;
            }
        }
        else{
            rev[d]=v;
            return 1;
        }
    }
    return 0;
}
void solve(){
    // build bipartite graph
    for(int j=1;j<=M;j+=2){
        foi(N){
            if(board[i][j]=='x') continue;
            for(int k=0;k<6;k++){
                int tr=i+dr[k];
                int tc=j+dc[k];
                if(inBoard(tr, tc)&&board[tr][tc]=='.') e[getIndex(i, j)].push_back(getIndex(tr, tc));
            }
        }
    }

    // maximum matching
    int maxMatch=0;
    foi(N*M){
        memset(visited, 0, sizeof(visited));
        if(match(i)) maxMatch++;
    }
    cout<<total_vertices-maxMatch<<endl;
}   

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
    cin>>C;
    while(C--){
        init();
        solve();
    }
}

Reference