[백준] 14500 - 테트로미노 (파이썬, Python)

 

https://pixabay.com/ko/photos/우산-햇빛-여자-비-빛-6239364/

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

14500번: 테트로미노

해당 문제의 분류는 구현입니다.

이 문제를 두 가지 종류의 해결하는 방법이 있는 거 같습니다.

 

1) 모든 테트로미노 경우의 수를 구하고 칸마다 대입해보기

2) 이동 거리를 4 칸으로 제한하고 탐색을 진행하기

 

저는 위 방법 중 2번 방법으로 시도했습니다.

 

제 코드는 아래와 같습니다.

해당 코드는 Python3로 제출 시 시간 초과가 발생하여 PyPy3로 제출했습니다.

전체 코드

import sys

def calculate(posList):
    global mat

    totVal = 0

    for pos in posList:
        cr = pos // M
        cc = pos % M

        totVal += mat[cr][cc]
    
    return totVal


def search(posList, depth):
    global answer

    if depth == 4:
        totVal = calculate(posList)
        if answer < totVal:
            answer = totVal
        return

    for pos in posList:
        cr = pos // M
        cc = pos % M
        
        for idx in range(3):
            newR = cr+dy[idx]
            newC = cc+dx[idx]

            if 0 <= newR < N and 0 <= newC < M and not newR * M + newC in posList:
                search(posList+[newR * M + newC], depth+1)

                
if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().strip().split())

    mat = [ list(map(int, sys.stdin.readline().strip().split())) for _ in range(N) ]
    
    dx = [1, 0, -1]
    dy = [0, 1, 0]
    answer = 0

    for i in range(N):
        for j in range(M):
            search([i*M+j], 1)

    print(answer)