[백준/BOJ] 11014번 : 컨닝 2 (+ 1014번 : 컨닝) (이분매칭, Platinum II)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 11014번 : '컨닝 2' (+ 1014번 : '컨닝) 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Platinum II이며, 문제를 해결하기 위해 이분 매칭 알고리즘에 대한 이해가 필요합니다.

 

 

11014번 : 컨닝 2

11014번: 컨닝 2

 

학생의 자리를 기준으로 왼쪽 위, 왼쪽, 오른쪽 위, 오른쪽 아래 자리는 컨닝이 가능하다고 할 때 아무도 컨닝을 하지 못하도록 배치할 수 있는 최대 학생 수를 구하는 문제입니다.

먼저 위치 관계에 대해 생각해보면 왼쪽 아래, 오른쪽 아래에 학생이 있으면 그 학생 것을 컨닝할 수는 없지만 그 학생이 컨닝을 할 수 있기 때문에 총 6방향의 위치에 인접하게 학생을 둘 수 없습니다.

 

그리고 자리의 연결성에 대해 생각해보면 한 학생은 왼쪽 줄과 오른쪽 줄만을 컨닝하므로, 홀수 열에 있는 학생들은 짝수 열에 있는 학생들만 컨닝할 수 있고, 짝수 열에 있는 학생들은 홀수 열에 있는 학생들만 컨닝할 수 있습니다.

 

따라서 짝수 열 자리와 홀수 열 자리를 두 그룹으로 생각하여 이분 그래프를 만들 수 있고, 그렇기 때문에 이분 매칭으로 문제를 해결할 수 있습니다.

자세한 설명은 아래 풀이 코드를 첨부 후에 설명드리겠습니다.

 

↓ 풀이 코드는 아래의 접은 글에 정리되어 있습니다.

#include <bits/stdc++.h>
using namespace std;
const int MSIZE = 85, MAX = 6405;

vector<int> Adj[MAX];
int Left[MAX], Right[MAX];
bool Visit[MAX];

bool DFS(int from) {
    Visit[from] = true;
    for(int i=0; i<Adj[from].size(); i++) {
        int to = Adj[from][i];
        if(Right[to] == -1 || (!Visit[Right[to]] && DFS(Right[to]))) {
            Left[from] = to, Right[to] = from;
            return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int T; cin >> T;
    while(T--) {
        for(int i=0; i<MAX; i++) vector<int>().swap(Adj[i]);

        int N, M, cnt = 0; cin >> N >> M;
        char Map[MSIZE][MSIZE];
        for(int i=1; i<=N; i++) {
            cin.clear();
            for(int j=1; j<=M; j++) {
                cin >> Map[i][j];
                if(Map[i][j] == '.') cnt++;
            }
        }

        int dir[2][6] = {{-1, 0, 1, -1, 0, 1}, {-1, -1, -1, 1, 1, 1}};
        for(int i=1; i<=N; i++)
            for(int j=1; j<=M; j++)
                for(int k=0; k<6; k++) {
                    if(Map[i][j] == 'x') continue;
                    int iNext = i + dir[0][k], jNext = j + dir[1][k];
                    if(iNext >= 1 && iNext <= N && jNext >= 1 && jNext <= M && Map[iNext][jNext] == '.')
                        Adj[(i-1)*80+j].push_back((iNext-1)*80+jNext);
                }

        int match = 0;
        fill(Left, Left+MAX, -1), fill(Right, Right+MAX, -1);
        for(int i=1; i<=N; i++)
            for(int j=1; j<=M; j+=2) {
                fill(Visit, Visit+MAX, false);
                if(DFS((i-1)*80+j)) match++;
            }

        cout << cnt - match << "\n";
    }
}

 

노드 번호는 자리를 1행 1열부터 오른쪽으로 1, 2, 3... 으로 번호를 매겼고 행 열의 수 관계없이 한 행의 크기를 max 값인 80으로 고정하고 계산하였습니다.

먼저 Map으로 자리의 상태를 입력받은 뒤, 각 자리를 기준으로 6가지 방향에 대해 검사합니다.

해당 방향에 x가 없어야하고 범위 역시 맵 밖으로 나가지 않아야 하며 이 모든 조건을 부합한다면 간선을 연결해줍니다.

 

간선 연결 후에는 모든 홀수 열의 자리를 기준으로 짝수 열로의 연결 관계를 확인하여 최대 매칭 수를 구해줍니다.

여기서 매칭이란 서로 컨닝이 가능한 두 자리이므로, 두 자리 중에 한 자리는 앉을 수 없음을 의미합니다.

즉 최대 매칭을 했을 때 간선의 수는 학생들을 최대한 앉혔을 때 앉을 수 없는 자리의 수이므로, 총 자리 수 - 최대 매칭 수가 답이 됩니다.

 

 

 

위의 풀이대로 코드를 작성하여 제출하면 위와 같은 기록으로 통과할 수 있습니다.

 

 

1014번 : 컨닝

1014번: 컨닝

 

위의 문제와 동일한 풀이로 이 문제 역시 해결할 수 있습니다.

이 문제는 위의 컨닝2의 축소판이기 때문에, 범위를 딱히 조정하지 않아도 같은 알고리즘으로 풀립니다.

 

 

 

동일한 코드를 제출하면 위와 같은 기록으로 정답 처리를 받을 수 있습니다.