백준 11014번: 컨닝2 (python)

by VICENTE97P4

Feb. 20, 2022, 1:49 p.m.

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

안녕하세요. 다른 문제로 찾아왔습니다.

이번에는 이분매칭에 관한 문제입니다.

사실 이분매칭은 코테에 나오는 알고리즘은 아닙니다.

코테에 나오기에는 너무 과하죠..

아마 평생 안나오지 않을까..

사실 이분매칭을 풀어봐야지 하고 찾은 문제가 아니라 비트마스킹 문제를 찾다가 발견한 문제입니다.

(컨닝1은 비트마스킹으로 풀 수 있습니다!!)

근데 비트마스킹으로 풀기에는 구현이 지저분하고, 너무 비효율적인 느낌이라.. 

결국 풀지 못하고 다른 분들의 풀이를 봤습니다.

알고보니 이분매칭으로 접근이 가능한 문제였습니다.

이분매칭은 알고나면 아하! 하는데, 이분매칭인걸 알아차리기가 힘듭니다..

이 문제도 그렇죠, 이걸 이분매칭을 어떻게 떠올릴 수 있나.. 싶습니다.

문제는 이렇습니다.

최백준의 시험장에서 다음과 같은 방향으로 컨닝이 가능하다고 합니다.

이때 아무도 컨닝을 못하게 앉힐 때 최대 몇 명을 앉힐 수 있는지를 구하는 문제입니다.

이걸 어떻게 풀 수 있을까요?

컨닝1 문제에서는 교실의 수가 적어서 비트마스킹으로 풀 수 있습니다.

앞 줄에 사람이 앉은 배치를 10110 이런 식으로 나타내어서 뒷 줄에 몇 명이 앉을 수 있는지 DP로 구할 수 있습니다.

그런데 이런 방식은 너무 비효율적입니다.

아니.. 안되는 경우가 너무 많은데 그걸 일일히 다 따지는게.. 뭔가 더 좋은 방법이 있을 것 같죠.

게다가 컨닝2는 교실의 크기가 커서 애초에 시간초과가 발생합니다.

그런데 이 문제는 이분매칭으로 풀 수 있습니다.

이분매칭이라고 정답을 들어도 어떻게 적용할지 떠오르지 않는데..

어떻게 해야 할까요?

사실 이 그림이 힌트였습니다.

컨닝을 할 수 있는 자리를 간선으로 이어봅시다.

그럼 두 그룹으로 나눌 수 있습니다.

왜냐하면 홀수 열에서 시작한 간선은 짝수 열에,

짝수 열에서 시작한 간선은 무조건 홀수 열에 이어지기 때문입니다.

차에서 그린 그림이라 그림이 개판이네요..

암튼 느낌만 보면 이런 느낌입니다.

그런데 이걸로 뭘 어쩌자는 거냐?

이분매칭의 최대 개수는 최소 간선 포함(Minimum Vertex Cover) 노드 개수와 같습니다.

이는 쾨잉의 정리에 증명되어있다고 합니다.

네.. 이걸 모르면 풀 수 없죠..

Minimum Vertex Cover는 모든 간선들을 포함하는 최소한의 노드들을 의미합니다.

위 그림에서 빨간 2개의 노드가 minimum vertex cover에 해당합니다.

위에서 컨닝이 가능한 관계를 간선으로 나타냈으니까 이 간선들이 이어지는 노드들을 다 없애주면 됩니다.

위 그림에서 홀수(왼쪽) 3개의 노드들을 없애도 컨닝할 수 있는 간선들이 이어지지 않지만,

최대한 많은 학생들을 앉히려면 짝수(오른쪽) 2개의 노드들을 없애는 것이 좋겠죠.

이 없애야 하는 노드들의 개수를 그냥 빡구현해서 구하려면 복잡하지만,

쾨잉의 정리 덕에 그냥 이분매칭만 해주면 됩니다.

그럼 전체 '좌석 수 - 이분매칭 수' 이 값이 정답이 됩니다.

코드를 봅시다.

import sys;input = sys.stdin.readline
C = int(input().strip())
di = [[-1, -1], [0, -1], [1, -1], [-1, 1], [0, 1], [1, 1]]


def DFS(a):
    global visited, even, odd

    visited.add(a)
    for b in graph[a]:
        if even[b] == -1 or ((even[b] not in visited) and DFS(even[b])):
            odd[a] = b
            even[b] = a
            return True

    return False


for ____ in range(C):
    N, M = map(int, input().split())
    desk = []
    for _ in range(N):
        desk.append(input().strip())
    graph = [[] for _ in range(N * M)]
    even, odd = [-1] * (N * M), [-1] * (N * M)
    total = 0
    for j in range(M):
        for i in range(N):
            if desk[i][j] == 'x':
                continue

            total += 1

            if j & 1:
                continue

            for dy, dx in di:
                ty = i + dy
                tx = j + dx
                if 0 <= ty < N and 0 <= tx < M and desk[ty][tx] == '.':
                    graph[i * M + j].append(ty * M + tx)

    ans = 0
    for j in range(0, M, 2):
        for i in range(N):
            visited = set()
            if DFS(i * M + j):
                ans += 1

    print(total - ans)

def DFS(a):
    global visited, even, odd

    visited.add(a)
    for b in graph[a]:
        if even[b] == -1 or ((even[b] not in visited) and DFS(even[b])):
            odd[a] = b
            even[b] = a
            return True

    return False

이 부분은 이분매칭 코드입니다.

알고리즘 강의가 아니므로 간략히만 설명한다면 일단 노드들을 매칭시키고,

다른 노드가 중복되어 매칭할 때, 먼저 매칭된 노드가 다른 노드로 매칭이 가능한지 살펴보고,

가능하면 먼저 매칭된 노드를 다른 노드와 매칭시키고, 불가능하면 그냥 둡니다.

    for j in range(M):
        for i in range(N):
            if desk[i][j] == 'x':
                continue

            total += 1

            if j & 1:
                continue

            for dy, dx in di:
                ty = i + dy
                tx = j + dx
                if 0 <= ty < N and 0 <= tx < M and desk[ty][tx] == '.':
                    graph[i * M + j].append(ty * M + tx)

이 부분은 간선을 만드는 코드입니다.

total은 전체 좌석 수를 셉니다.

            if j & 1:
                continue

이 부분은 짝수 열을 건너뛰기 위한 코드입니다.

홀수 열을 기준으로 매칭을 시켜줄 것이기 때문에, 짝수 열에서 시작하는 간선은 추가해주지 않아도 됩니다.

이는 이분매칭 구현 상 짝수 열에서 시작하는 간선은 불필요하기 때문입니다.

    ans = 0
    for j in range(0, M, 2):
        for i in range(N):
            visited = set()
            if DFS(i * M + j):
                ans += 1

    print(total - ans)

모든 홀수 열에 있는 노드들을 기준으로 매칭을 시작해줍니다.

전체 좌석 수에서 매칭 성공 수를 빼주면 정답입니다.

di = [[-1, -1], [0, -1], [1, -1], [-1, 1], [0, 1], [1, 1]]

di는 컨닝이 가능한 방향을 나타낸 리스트입니다.

그런데 컨닝이 가능한 방향은 4개인데 리스트에는 왜 6개가 있을까요?

바로 대각선 왼쪽 뒤와 대각선 오른쪽 뒤 방향까지 넣었기 때문입니다.

이렇게요..

엥? 갑자기 이 두 방향을 왜 넣을까요?

그건 제가 한 구현대로라면 예외인 경우가 생기기 때문입니다.

제 알고리즘은 홀수 열을 기준으로 이분매칭을 시작했습니다.

그럼 다음과 같은 예외가 생깁니다.

. . .
. . .
x . x

이 경우에는 정답이 4입니다. 하지만 제 구현 상에는 5가 정답이 됩니다.

왜냐하면 마지막 줄 가운데 부분에는 이어진 간선이 없어져서

매칭 불가능하다고 판단하고 7 - 2 = 5가 나오게 됩니다.

이는 홀수 열만 이분매칭을 실행해서 생긴 예외입니다.

홀수 열의 입장에서는 이어질 수 없지만 짝수 열의 입장에서는 이어질 수 있기 때문에

이와 같은 경우까지 생각해주기 위해 2 방향을 추가적으로 넣어주었습니다.

저는 이걸 찾지 못해서 한참을 고민하고 틀렸습니다..

이분매칭을 짝수 열의 입장에서 실행하지 않더라도 고려해줘야 했습니다..

어려운 문제입니다.

사실 이분매칭이라는 알고리즘을 모르면 아예 이해할 수 없는 문제인데,

제가 알고리즘에 대한 설명을 하지 않아서 이해하기 힘들었을 수 있습니다.

이분매칭에 대한 자세한 설명은 다른 블로그(특히 Ries님)를 찾아보시면 자세히 나와있습니다.

이분매칭은 알아차리면 꽤 쉬운데 알아차리고 적용하기가 힘든 것 같습니다.

오랫동안 고민해보고, 삽질해보고, 결국 풀어내지 못하더라도,

다른 분들의 풀이를 보면서 깨우치고 방법을 배우는 것이 재밌습니다.

역시 세상은 넓고 방법은 다양하고 배워야할 것은 많습니다.

재밌는 문제였습니다.