백준 1014 <컨닝> / 11014 <컨닝 2> Python

https://www.acmicpc.net/problem/1014

https://www.acmicpc.net/problem/11014

---

해당 문제는 최소 버텍스 커버 문제입니다.

 

해당 문제에서 학생 -> 학생 의 버텍스 (엣지) 는 커닝의 가능성으로 볼 수 있습니다.

즉 모든 버텍스를 커버하면 커닝의 가능성이 있는 모든 위치를 탐색하는 것과 동일합니다.

그러므로 모든 버텍스를 커버하고 남는 자리에 학생을 앉히면 커닝을 당하거나 할 가능성이 없습니다.

 

해당 문제에서 특정 위치에 학생을 앉힌다고 가정하면 해당 학생과 같은 열에 있는 학생은 커닝을 당할일도 할 일도 없습니다. 즉 어떤 학생에게서 다른 학생에게 향하는 버텍스는 짝수 -> 홀수 / 홀수 -> 짝수 의 두 경우로 나뉩니다. 그러므로 해당 문제의 그래프는 홀수열 / 짝수열의 두 그룹으로 나눌 수 있는 이분그래프입니다.

 

이분그래프에서 최소 버텍스 문제라면

백준 1867 <돌멩이 제거> Python

해당 문제와 같은 경우로 쾨닉의 정리에 따라 문제의 해와 같은 문제를 이분매칭 했을 때의 해가 같습니다.

 

즉 '짝수 / 홀수 열로 나눈 이분그래프에서 이분매칭의 답을 구하면 최소 버텍스 커버의 답을 찾을 수 있고 해당 답은 앉을 수 없는 자리이므로 제외하고 다른자리에 모두 앉히면 된다' 가 되겠습니다.

 

짝수 -> 홀수 로 이분매칭을 했다면 짝수열에는 모두 학생이 앉을 수 있고

홀수 -> 짝수 로 이분매칭을 했다면 홀수열에는 모두 학생이 앉을 수 있으므로

전체 자리수 - 매칭 된 수 가 답이 되겠습니다.

---

import sys

input = sys.stdin.readline

# 이분매칭

def bimatch(idx, connectable, connected, visited):

    # 이미 방문했으면 패스

    if visited[idx]:

        return False

   

    # 방문 체크

    visited[idx] = True

    # 순회

    for node in connectable[idx]:

        # 매칭할 수 있거나 다른 노드와 매칭시킬 수 있으면

        if connected[node] < 0 or bimatch(connected[node], connectable, connected, visited):

            # 매칭

            connected[node] = idx

            return True

   

    return False

def solution(N, M, tables):

    # 매칭될 수 있는 리스트(짝수 -> 홀수)

    connectable = [[] for _ in range(((M+1)//2) * N)]

    # 매칭된 리스트(홀수 -> 짝수)

    connected = [-1 for _ in range((M//2) * N)]

    # 탐색 가이드 / [1, -1] 과 [1, 1] 은 상대가 나를 볼 수 있으므로 탐색

    search_guide = [[-1, -1], [0, -1], [1, -1], [-1, 1], [0, 1], [1, 1]]

    # 순회

    for n in range(N):

        # 짝수만 순회

        for m in range(0, M, 2):

            # 현재 위치가 앉을 수 있는 위치면

            if tables[n][m] == '.':

                # 현재 위치에서 앉을 수 없는 자리 탐색

                for i, j in search_guide:

                    # 탐색 인덱스

                    nn = n+i

                    nm = m+j

                    # 탐색 인덱스가 범위 내에 있고 앉을 수 있다면

                    if (nn >= 0 and nn < N) and (nm >= 0 and nm < M) and (tables[nn][nm] == '.'):

                        # 탐색 가능 리스트에 추가

                        # 짝수 / 홀수 인덱스를 압축해 연속된 인덱스로 표현

                        connectable[(m//2) * N + n].append((nm//2) * N + nn)

    # 순회

    for idx in range(len(connectable)):

        # 방문 목록

        visited = [False for _ in range(len(connectable))]

        # 이분매칭

        bimatch(idx, connectable, connected, visited)

   

    # 매칭된 수

    matched = sum([1 for c in connected if c >= 0])

    # 전체 자리수

    table_num = 0

    for row in tables:

        table_num += sum([1 for r in row if r=='.'])

   

    print(table_num - matched)

# 입력

C = int(input().strip())

for _ in range(C):

    N, M = map(int, input().strip().split())

    tables = [list(input().strip()) for _ in range(N)]

   

    solution(N, M, tables)