PS/Python
[백준] 14500 - 테트로미노 (파이썬, Python)
w00se
2021. 6. 5. 13:53
https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변
www.acmicpc.net
해당 문제의 분류는 구현입니다.
이 문제를 두 가지 종류의 해결하는 방법이 있는 거 같습니다.
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)