Coding Test/BaekJoon_Python

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

JunOnJuly 2024. 10. 16. 15:23
728x90

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

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


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

 

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

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

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

 

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

 

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

 

백준 1867 <돌멩이 제거> Python

https://www.acmicpc.net/problem/1867'해당 문제는 이분매칭 알고리즘을 사용하는 문제입니다.'라고 말하면 왜인지 다들 화가 날 것 같습니다. 저는 화가 났습니다. 왜냐하면 이 문제는 단순한 이분매칭

dev-diary-0717.tistory.com

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

 

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

 

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

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

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


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)

 

728x90