[백준] 1014 - 컨닝 (Python)

두 가지 해결방법이 있다.
첫번째는 비스마스킹을 이용한 동적 계획법이다.

모든 학생이 앞의 행 왼쪽부터 순서대로 앉는다고 가정한다.
각각의 학생이 앉을지 결정하는 시점에는 앞쪽 대각선과 왼쪽 자리만 체크하면 된다.

이 경우, 가능한 학생들의 배치가 오직 바로 앞의 배치에 종속된다. 따라서 학생들의 배치를 비트마스킹으로 표현하고, 동적 계획법을 사용하면 된다.

import sys
input = sys.stdin.readline

# 학생들을 r행에 배치 가능한 경우를 체크
def check_seat(r):
	# 첫번째 행은 이전 배치가 아무것도 없는 상태
    if r == 0:
        prev_bm_arr = [0]
    # 바로 앞 행의 배치
    else:
        prev_bm_arr = arr_bm[r-1]
    # 학생들의 가능한 모든 배치를 저장
    next_bm = set()
    
    # 이전의 모든 배치에 대해 고려
    for prev_bm in prev_bm_arr:
    	# 해당 값으로 배치된 모든 학생수
        if r == 0:
            prev_num = 0
        else:
            prev_num = dp[r-1][prev_bm]
        # 현재 배치와 배치된 학생수
        cur_bm = [0]
        num_bm = [0]
        for i in range(m):
            if graph[r][i] == 'x':
                continue
            # 현재 가능한 모든 배치를 갱신
            for j in range(len(cur_bm)):
                bm = cur_bm[j]
                num = num_bm[j]
                # 왼쪽과 왼쪽 앞 대각선 체크
                if i-1 >= 0:
                    temp = 1<<i-1
                    if bm & temp or prev_bm & temp:
                        continue
                # 오른쪽 앞 대각선 체크
                if i+1 < m:
                    temp = 1<<i+1
                    if prev_bm & temp:
                        continue
                cur_bm.append(bm|1<<i)
                num_bm.append(num+1)
        # 가능한 모든 배치들에 대해 최대 학생수를 갱신
        for i in range(len(cur_bm)):
            bm = cur_bm[i]
            num = num_bm[i]
            dp[r][bm] = max(dp[r][bm], prev_num+num)
        next_bm.update(cur_bm)
    # 현재 배치들을 다음 행에서 사용하기 위해 저장
    arr_bm[r] = list(next_bm)

t = int(input())
for _ in range(t):
    n, m = map(int, input().rstrip().split())
    dp = [[0]*2**m for _ in range(n)]
    arr_bm = [[] for _ in range(n)]
    graph = [input() for _ in range(n)]
    for i in range(n):
        check_seat(i)
    print(max(dp[n-1]))

---

두번째는 최소 정점 커버를 사용하는 것이다.

최소 정점 커버란 그래프의 모든 간선들과 연결가능한 정점들의 집합 중 가장 작은 크기를 갖는 것을 말한다.
최소 정점 커버에 속한 정점들을 모두 제거하면 나머지 정점들의 모든 연결이 끊기게 된다.

최소 정점 커버를 구하기 위해서는 이분 매칭을 사용하면 된다.
모든 자리를 정점으로 보고, 컨닝이 가능한 자리끼리 간선으로 연결한다고 가정해보자.

컨닝조건을 생각하면, 바로 앞사람과 뒷사람과는 절대 컨닝을 할 수 없다. 또한 옆으로 두 칸 떨어진 사람과도 마찬가지다.
이때 모든 홀수 열 자리는 서로 간선이 존재하지 않고, 짝수 열 자리도 마찬가지다. 따라서 이분 매칭이 가능하다.

이렇게 구한 최소 정점 커버는 무엇을 뜻할까?
이 그래프에서 간선은 컨닝가능한 정점을 연결하고 있다.
따라서 모든 정점에서 최소 정점 커버를 제거하면 서로 컨닝이 불가능한 자리의 최대값을 구할 수 있다.

import sys
input = sys.stdin.readline

# 이분 매칭
def bip_match(x, y):
	# 컨닝가능한 6방향 체크
    for i in range(len(d_x)):
        dx = x+d_x[i]
        dy = y+d_y[i]
        if not (0 <= dx < n and 0 <= dy < m):
            continue
        # 이미 완료된 정점은 시도하지 않음
        if graph[dx][dy] == 'x' or done[dx][dy]:
            continue
        done[dx][dy] = 1
        # 점유한 정점이 없거나 양보가 가능한 경우
        if not link[dx][dy] or bip_match(*link[dx][dy]):
            link[dx][dy] = [x, y]
            return 1
    return 0
    
t = int(input())
d_x = [-1, 0, 1, -1, 0, 1]
d_y = [-1, -1, -1, 1, 1, 1]
for _ in range(t):
    n, m = map(int, input().rstrip().split())
    graph = [input() for _ in range(n)]
    # 
    link = [[0]*m for _ in range(n)]
    # 앉을 수 있는 자리의 최대값
    seat_num = n*m
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 'x':
                seat_num -= 1
                continue
            if not j%2:
                continue
            done = [[0]*m for _ in range(n)]
            # 매칭이 되었다면 앉을 수 없는 자리임
            seat_num -= bip_match(i, j)
    print(seat_num)