백준 테트로미노 [14500] Python 코드 + 해설

백준 테트로미노 14500 파이썬(python) 코드 및 해설입니다.( DFS와 브루트 포스 )

백준 14500 테트로미노 문제

 

• **DFS(깊이 우선 탐색)**를 사용하여 모든 가능한 모양을 탐색한다.
• 'ㅗ' 모양은 DFS로 탐색할 수 없으므로 별도로 처리한다.
• 경계 조건을 명확히 확인하여 인덱스 오류를 방지한다.
• 최적화를 위해 가지치기를 사용한다.

구현 단계

1. 입력 받기
   • 종이의 크기 N, M과 종이에 쓰인 수들을 입력받는다.
   • 종이의 정보를 2차원 리스트 board에 저장한다.
2. DFS 함수 구현
   • 현재 위치에서 깊이 4까지 탐색하여 가능한 모든 모양의 합을 계산한다.
   • 이미 방문한 위치를 재방문하지 않도록 visited 배열을 사용한다.
   • 백트래킹을 통해 방문 상태를 원래대로 복구한다.
   • 가지치기를 위해 남은 칸에서 얻을 수 있는 최대 값을 미리 계산하여 합산해도 현재 최대 합을 넘지 못하면 탐색을 중단한다.
3. 'ㅗ' 모양 별도 처리
   • DFS로는 'ㅗ' 모양을 만들 수 없으므로, 모든 위치에서 'ㅗ' 모양의 4가지 형태를 직접 검사한다.
   • 각각의 모양에 대해 범위를 벗어나지 않는지 확인하고 합을 계산한다.
4. 최대 합 갱신
   • 모든 탐색 과정에서 계산된 합이 현재 최대 합보다 크면 갱신한다.
5. 결과 출력
   • 모든 탐색이 끝나면 최대 합을 출력한다.

최종 정답 코드 파이썬(Python)

import sys
sys.setrecursionlimit(100000)

input = sys.stdin.readline

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
max_sum = 0

visited = [[False]*M for _ in range(N)]
dx = [-1, 1, 0, 0]  # 상, 하, 좌, 우
dy = [0, 0, -1, 1]

max_val = max(map(max, board))  # 보드에서 가장 큰 값

def dfs(x, y, depth, total):
    global max_sum
    # 가지치기: 현재 합 + 남은 칸에서 얻을 수 있는 최대 값 * 남은 깊이 <= 현재 최대 합이면 탐색 중단
    if total + max_val * (4 - depth) <= max_sum:
        return

    if depth == 4:
        max_sum = max(max_sum, total)
        return

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
            visited[nx][ny] = True
            dfs(nx, ny, depth + 1, total + board[nx][ny])
            visited[nx][ny] = False

for i in range(N):
    for j in range(M):
        visited[i][j] = True
        dfs(i, j, 1, board[i][j])
        visited[i][j] = False

        for k in range(4):
            temp = board[i][j]
            for t in range(3):
                idx = (k + t) % 4
                nx = i + dx[idx]
                ny = j + dy[idx]
                if 0 <= nx < N and 0 <= ny < M:
                    temp += board[nx][ny]
                else:
                    break
            else:
                max_sum = max(max_sum, temp)

print(max_sum)

 

모든 경우를 시도해보는 것이 가능할 때는 가장 확실한 방법이다. 특히 DFS와 백트래킹, 가지치기를 잘 활용하면 효율적으로 탐색할 수 있다.

정답 14500 테트로미노