Baekjoon 14500. 테트로미노 / Python

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

문제 설명

n * m 크기의 종이에 테트로미노 하나를 놓아 테트로미노가 놓인 칸들의 수들의 합을 최대로 만들어야 한다.

회전, 대칭이 가능하다.

코드 설명

 

• DFS 함수 구현:
  • dfs 함수는 재귀적으로 테트로미노의 각 칸을 탐색한다.
  • 현재까지의 합 sums와 탐색한 칸의 수 cnt를 추적한다.
  • 가지치기를 통해 가능성이 없는 경로는 미리 차단한다.
  • 상하좌우로 이동하면서 테트로미노의 모양을 형성한다.
  • ㅗ 모양의 테트로미노를 만들기 위해 두 번째 칸에서 다시 시작하는 경우도 고려한다.
• 최대 합 계산:
  • 모든 칸을 시작점으로 하여 DFS를 수행하고, 최댓값을 갱신한다.
  • 최종적으로 최대 합을 출력한다.
  • 시간복잡도 : O(N * M * 256)

 

 

import sys
input = sys.stdin.readline

# N: 종이의 세로 크기, M: 종이의 가로 크기
n, m = map(int, input().strip().split())

# board: 종이의 각 칸에 쓰여있는 수
board = []
board_max = -1

# 종이의 각 행을 입력받아 board에 저장하고, 가장 큰 수 board_max를 갱신
for _ in range(n):
    line = list(map(int, input().strip().split()))
    board_max = max(board_max, max(line))
    board.append(line)

def dfs(total, tmp, start, sums, cnt):
    global max_cnt
    x, y = start
    s = total[x][y]

    # 현재까지의 합과 남은 칸의 최대 값을 고려하여 가지치기
    if sums + total[x][y] + board_max * (3 - cnt) < max_cnt:
        return

    # 테트로미노가 4칸이 된 경우, 최대 값 갱신
    if cnt == 3:
        sums += total[x][y]
        if sums > max_cnt:
            max_cnt = sums
        return

    # 상하좌우로 이동
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    for d in directions:
        next_x = x + d[0]
        next_y = y + d[1]

        # 이동 가능한 범위 확인 및 방문 여부 확인
        if 0 <= next_x < n and 0 <= next_y < m and not tmp[next_x][next_y]:
            next_point = [next_x, next_y]

            # ㅗ 모양을 위해 두 번째 칸에서 다시 시작하는 경우 처리
            if cnt == 1:
                tmp[next_x][next_y] = True
                dfs(total, tmp, start, sums + total[next_x][next_y], cnt + 1)
                tmp[next_x][next_y] = False

            tmp[next_x][next_y] = True
            dfs(total, tmp, next_point, sums + s, cnt + 1)
            tmp[next_x][next_y] = False

# 최대 합 저장 변수
max_cnt = -1

# 방문 여부 체크 리스트
check = [[False] * m for _ in range(n)]

# 각 칸을 시작점으로 하여 DFS 수행
for i in range(n):
    for j in range(m):
        check[i][j] = True
        dfs(board, check, (i, j), 0, 0)
        check[i][j] = False

# 최종 결과 출력
print(max_cnt)

 

visited 배열을 사용했다면 좀 더 효율적이었을 것 같다.........