파이썬으로 풀어보는 백준 14500번: 테트로미노 (삼성 A형 기출 문제)

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

14500번: 테트로미노

 

내 풀이:

def make_block(idx, y, x, visited):
    global ans
    new = visited[:]
    new.append([y, x])
    if idx == 3:
        result = 0
        for co in new:
            result += arr[co[0]][co[1]]
 
        if ans < result:
            ans = result
        return
 
    lst = []
    for dir in range(3):
        ny = y + dy[dir]
        nx = x + dx[dir]
 
        if 0 <= ny <= N - 1 and 0 <= nx <= M - 1 and [ny, nx] not in new:
            make_block(idx+1, ny, nx, new)
            lst.append(arr[ny][nx])
 
    if idx == 0:
        if 0 <= y-1:
            lst.append(arr[y-1][x])
 
        if len(lst) == 4:
            result = sum(lst) - min(lst) + arr[y][x]
            if ans < result:
                ans = result
 
        elif len(lst) == 3:
            result = sum(lst) + arr[y][x]
            if ans < result:
                ans = result
 
 
N, M = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
 
dy = [0, 1, 0]
dx = [1, 0, -1]
ans = 0
for i in range(N):
    for j in range(M):
        make_block(0, i, j, [])
 
print(ans)

Python3, 7628ms

재귀함수를 이용하여 좌우와 아래쪽 3방향만 탐색하여 중복으로 만들어지는 도형을 최대한 줄이고자 하였다. 아마도 사각형 모양의 블록을 제외하고는 중복하는 블록은 나타나지 않을 것이다. 문제가 ㅗ모양 테트로미노인데 재귀로 한번에 탐색하는 것이 불가능하기 때문에 첫 조각을 선택 후 주변을 살펴서 3개, 4개의 공간이 있으면 그에 따른 최대값을 계산하는 방식으로 알고리즘을 구현하였다.