[백준 문제] P14500 테트로미노 (파이썬)

15 Feb 2020 in Algorithm on 백준알고리즘

[백준 문제] P14500 테트로미노 (파이썬)

내 풀이는 처음에 모든 테트리스 경우를 만들어서 하는 방법 pypy로 제출할 경우 성공
다른 사람들은 어떻게 푸나 봤더니 모든 우의 수를 손으로 다 계산해서 하는 방법으로 품

내 풀이

import sys

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

for i in range(3):
    for j in range(4):
        giuk = [[0, 0], [0, 1], [1, 1]]
        a = [giuk[i][0] + dx[j], giuk[i][1] + dy[j]]
        giuk.append(a)
        case_lst = list(set(map(tuple, giuk)))
        all_lst.append(case_lst)

for i in range(3):
    for j in range(4):
        giuk = [[0, 0], [0, 1], [1, 0]]
        a = [giuk[i][0] + dx[j], giuk[i][1] + dy[j]]
        giuk.append(a)
        case_lst = list(set(map(tuple, giuk)))
        all_lst.append(case_lst)

for i in range(3):
    for j in range(4):
        giuk = [[0, 0], [1, 0], [1, 1]]
        a = [giuk[i][0] + dx[j], giuk[i][1] + dy[j]]
        giuk.append(a)
        case_lst = list(set(map(tuple, giuk)))
        all_lst.append(case_lst)

for i in range(3):
    for j in range(4):
        giuk = [[1, 0], [0, 1], [1, 1]]
        a = [giuk[i][0] + dx[j], giuk[i][1] + dy[j]]
        giuk.append(a)
        case_lst = list(set(map(tuple, giuk)))
        all_lst.append(case_lst)

all_lst = list(set(map(tuple, all_lst)))

all_del_lst = []
for i in all_lst:
    if len(i) == 4:
        all_del_lst.append(i)

all_del_lst.append(((0,0),(0,1),(0,2),(0,3)))
all_del_lst.append(((0,0),(1,0),(2,0),(3,0)))

n, m = map(int, sys.stdin.readline().split())

arr = []
for _ in range(n):
    arr.append(list(map(int, sys.stdin.readline().split())))
ans = 0

## 문제 풀이
def check(a):
    if a[0] >= 0 and a[0] < n and a[1] >= 0 and a[1] < m:
        return True
    else :
        return False


for i in range(n) :
    for j in range(m) :
        for k in all_del_lst :
            sum = 0
            cnt = 0
            for l in k :
                p = [0,0]
                p[0] = l[0] + i
                p[1] = l[1] + j
                if check(p) :
                    sum += arr[p[0]][p[1]]
                    cnt += 1
            if cnt == 4:
                ans = max(ans, sum)

print(ans)

다른 사람 참고 풀이

참고 사이트

해결 순서

모든 경우의 수를 최초자리 (0,0)으로 19개의 경우의 수를 만듬
테트로미노 데피니션을 만들어서 최초 자리를 기점으로 모든 경우의수를 다 돌려보고 없는 자리가 나오면 except Indexerror로 continue해서 계속 돌게 마듬
N, M값만 지정해주면 답 구해줌

# 속도 빠르게 하기위해
from sys import stdin
input = stdin.readline


n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
# 최초자리를 (0,0)으로 모든 경우의수를 구함 19개
b = [
    [(0,1), (1,0), (1,1)],
    [(0,1), (0,2), (0,3)],
    [(1,0), (2,0), (3,0)],
    [(0,1), (0,2), (1,0)],
    [(0,1), (0,2), (-1,2)],
    [(1,0), (1,1), (1,2)],
    [(0,1), (0,2), (1,2)],
    [(1,0), (2,0), (2,1)],
    [(0,1), (1,1), (2,1)],
    [(0,1), (1,0), (2,0)],
    [(1,0), (2,0), (2,-1)],
    [(1,0), (1,1), (2,1)],
    [(0,1), (1,0), (-1,1)],
    [(0,1), (1,0), (1,-1)],
    [(0,1), (1,1), (1,2)],
    [(0,1), (0,2), (1,1)],
    [(1,0), (1,1), (1,-1)],
    [(1,0), (2,0), (1,-1)],
    [(1,0), (1,1), (2,0)]
]

def tetromino(x, y):
    global ans
    for i in range(19):
        s = a[x][y]
        for j in range(3):
            try:
                nx = x+b[i][j][0]
                ny = y+b[i][j][1]
                s += a[nx][ny]
            # 자리가 없어서 결과값이 안나올 수도 있으니
            except IndexError:
                continue
        # 19번을 뭐가 맥스인지
        ans = max(ans, s)

def solve():
    for i in range (n):
        for j in range(m):
            tetromino(i, j)

ans = 0
solve()
print(ans)