백준 14500 테트로미노 파이썬 (무식한 방법)

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

14500번: 테트로미노

처음 이 문제를 봤을때는 dfs(i,j,c,sums)에서 연산 횟수 c+1 , sums에 값을 더해주고 하고  c==4가 되는 경우의 sums를 모두 저장한 다음에 최댓값을 출력하는 함수로 만들었지만 예제 출력에도 한참이 걸렸고 그 이유가 중복되는 블록까지도 계속 더하고 연산하는 것을 발견해서 오래 걸린 것이라고 생각했다.

 

그래서 차라리 주어진 테트로미노가 나올 수 있는 모양을 일일이 구해서 그것만 dfs를 돌린다면 시간을 획기적으로 줄일 수 있겠다고 판단했고 나올 수 있는 모든 블럭의 경우의 수(19가지)를 구해서 dx dy 테크닉을 사용했다.

 

추가로 시간을 줄이기 위해 연산도중에 0~N과 0~M의범위를 벗어나면 바로 break를 걸어줬고 시간을 줄이기 위해  dx dy테크닉 배열에 절댓값이 큰 숫자부터 넣어줬다. 

 

다음에는 다른 방법으로 한번 풀어봐야겠다.

 

++)대부분의 블럭을 4개의 방향으로 돌렸는데 저기 주황색 블럭은 대칭까지 포함해서 8개 종류가 나올 수 있다.

 

import sys
input = sys.stdin.readline
def dfs(i,j):
    global count
    for k in range(19):
        kx = d2x[k]
        ky = d2y[k]
        counts =0
        e = 0
        for q in range(4):
            nx = i+kx[q]
            ny = j+ky[q]
            if 0<=nx<n and 0<=ny<m:
                counts+=s[nx][ny]
            else:
                e=1
                break
        if e==0:
            count = max(count,counts)
d2x = [[0,0,0,0],[3,2,1,0],[1,1,0,0],[2,1,0,0],[0,0,0,1],[2,2,1,0],[-1,0,0,0],[2,1,1,0],[2,1,1,0],[1,1,0,0],[-1,-1,0,0],[0,1,0,0],[0,-1,0,0],[1,-1,0,0],[1,-1,0,0],[2,2,1,0],[-1,0,0,0],[-2,-2,-1,0],[1,0,0,0]]
d2y = [[3,2,1,0],[0,0,0,0],[1,0,1,0],[1,1,1,0],[2,1,0,0],[1,0,0,0],[2,2,1,0],[1,1,0,0],[-1,-1,0,0],[2,1,1,0],[2,1,1,0],[2,1,1,0],[2,1,1,0],[0,0,1,0],[0,0,-1,0],[-1,0,0,0],[-2,-2,-1,0],[1,0,0,0],[2,2,1,0]]

n,m = map(int,input().split())
s=[list(map(int,input().split())) for _ in range(n)]
vist = [[False]*m for _ in range(n)]
count = -1
for i in range(n):
    for j in range(m):
        dfs(i,j)
print(count)

도움이 되셨으면 공감 한번씩만 눌러주세요 로그인 필요 X