Baekjoon 11014. 컨닝 2 / Python

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

11014번: 컨닝 2

• 같은 코드로 1014. 컨닝 도 풀린다.

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

1014번: 컨닝

- 함수 설명

1. sol() : 내가 컨닝할 수 있거나, 컨닝당할 수 있는 위치에, 방문하지 않았고, 앉을 수 있다면 재귀적으로 다시 매칭을 시도하는 함수

- 알고리즘 설명

1. dp를 사용하여 모든 점의 매칭 상태를 [-1, -1]로 만들어준다.

2. 격자의 짝수 열의 모든 점에 대해 매칭을 시도한다. visit을 사용하여 방문 여부를 기록한다.

3. 이분 매칭을 활용한 풀이 방식으로 이분 매칭 알고리즘에 대한 이해를 한다면 좋은 문제.

def sol(x, y):
    # 6개의 방향 (상하, 좌상, 좌하, 우상, 우하)으로 이동
    for dx, dy in [(0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]:
        nx, ny = x + dx, y + dy  # 새로운 좌표 계산
        # 새로운 좌표가 격자 범위 내에 있고, 방문하지 않았으며, 앉을 수 있는 자리인 경우
        if nx in range(n) and ny in range(m) and not visit[nx][ny] and arr[nx][ny]:
            visit[nx][ny] = 1  # 방문 처리
            # 새로운 좌표에 매칭이 없거나 (기본 값 [-1, -1])
            # 재귀적으로 새로운 좌표에서 매칭을 찾을 수 있는 경우
            if dp[nx][ny] == [-1, -1] or sol(dp[nx][ny][0], dp[nx][ny][1]):
                dp[nx][ny] = [x, y]  # 매칭 갱신
                return 1  # 매칭 성공
    return 0  # 매칭 실패

import sys
input = sys.stdin.readline  


for _ in range(int(input())):
    n, m = map(int, input().split())  # 교실의 크기
    arr = [list(input().strip()) for _ in range(n)]  # 교실 좌표
    res = 0  # 앉을 수 있는 최대 학생 수
    
    # 입력된 교실을 숫자 배열로 변환
    for i in range(n):
        for j in range(m):
            if arr[i][j] == '.':  # '.'을 1로 변환 (앉을 수 있는 자리)
                arr[i][j] = 1
                res += 1  # 앉을 수 있는 자리의 수 증가
            else:  # 장애물인 경우
                arr[i][j] = 0
    
    dp = [[[-1, -1] for _ in range(m)] for __ in range(n)]  # 매칭 정보를 저장할 배열
    
    # 격자의 모든 점에 대해 매칭 시도
    for i in range(n):
        for j in range(0, m, 2):  # 짝수 열에 대해서만 시도 (한쪽 파트만 탐색)
            if arr[i][j]:  # 앉을 수 있는 자리인 경우
                visit = [[0] * m for _ in range(n)]  # 방문 배열 초기화
                if sol(i, j):  # 매칭 시도
                    res -= 1  # 매칭 성공 시 결과 감소 

    print(res)  # 최종 배치 가능한 최대 학생 수 출력