[Python][백준] 14500번 테트로미노

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

공부 날짜 : 2022.08.26
정답 참조 여부:O

테트리스게임에 나오는 블록을 테트로미노라고 하며 이 블록을 특정 매트위에 올렸을때 그 값의 합이 최대가 되는 문제를 구하는 내용이다.

처음 문제를 봤을때 19가지 경우의 수를 모두 매트위에 올려보며 하는 방법을 떠올렸으나 역시나 실패
오답은 아니라고 생각하지만 시간초과가 떴다.
어느정도 수정을 거치면 19가지 모두써서 문제를 풀 수 있을것 같지만 출제의도는 아닌게 뻔했으므로 1번만 시도해보고 바로 정석으로 풀었다.

본인이 생각하는 정석적인 방법은 dfs로 푸는 것이었는데 아무리 봐도 ㅗㅏㅓㅜ 모양은 다른 모양들과 같은 dfs로는 구하는게 불가능해서 정답을 참조해보니 그냥 따로 계산하는 방법이 있었다.
간단하게 가운데를 기준으로 4가지 방향을 모두보며 한방향씩 제외해서 ㅗㅏㅓㅜ 모양은 쉽게 비교 할 수 있었다.

ㅗㅏㅓㅜ 를 제외한 15가지 모양은 4가지 방향으로 dfs를 구현하되 count가 4이면 return하여 최대값을 비교하는 방식으로 했으나 어떻게 해도 시간초과가 나왔다.

정답을 참고한 결과 진행하고 있는 방법이 최대가 되는 것이 불가능하면 return하는 방법을 추가 했는데 데이터에서 최대값을 미리 저장해두고 현재 값에 최대값을 남은 수만큼 더해도 현재 저장된 최대값보다 낮으면 return 해 주었다.

max_val = max(map(max, data))

if result >= add_result + (max_val * (4-count)):
        return

아래 소스코드에 #######으로 표시한 부분이 정답을 참고한 부분이다.

소스코드

import sys
input = sys.stdin.readline

n,m = map(int, input().split())

data = []
for _ in range(n):
    data.append(list(map(int,input().split())))

#############################
max_val = max(map(max, data))
#############################
visit = [[False]*m for _ in range(n)]

dx = [0,1,0,-1]
dy = [1,0,-1,0]

result = 0

#ㅏㅓㅗㅜ제외한 15가지를 체크
def dfs(x,y,count,add_result):
    global result
    ###############################################
    if result >= add_result + (max_val * (4-count)):
        return
    ###############################################
    if count == 4:
        result = max(result,add_result)
        return
    
    for dir in range(4):
        nx = x+dx[dir]
        ny = y+dy[dir]
        
        
        if nx >= 0 and nx < n and ny >= 0 and ny < m and not visit[nx][ny]:
            visit[nx][ny] = True
            dfs(nx,ny,count+1,add_result+data[nx][ny])
            visit[nx][ny] = False
            
#ㅏㅓㅗㅜ체크
def find_other(x,y):
    global result

    for i in range(4):
        add_result = data[x][y]
        for j in range(3):
            dir = (i+j) % 4
            
            nx = x+dx[dir]
            ny = y+dy[dir]
            
            if not(nx >= 0 and nx < n and ny >= 0 and ny < m):
                break
            add_result += data[nx][ny]
                
                
        result = max(result,add_result)

        
for i in range(n):
    for j in range(m):
        visit[i][j] = True
        dfs(i,j,1,data[i][j])
        visit[i][j] = False
        
        find_other(i,j)
        
print(result)

배운점

dfs나 bfs등 완전 탐색을 할 때 해당 연산을 할 필요성이 있는지 판단해서 연산을 안하면 수행시간을 단축할 수 있다.
한가지 방법으로 모든 경우를 볼 필요는 없고 예외가 있다면 예외를 따로 처리해주는 방법도 가능하다.