[파이썬] 백준 14500 테트로미노

빠진 조건 없게 구현을 했고, 테스트 케이스는 통과를 했지만 실제 채점에서는 시간 초과가 나왔다. BFS 가 아닌 모든 도형 모양에 따른 최댓값으로 구해도 정답이 나온다고 한다. 

import sys
from collections import deque
import copy
 
def bfs(x1,y1,k,a,b):
 
    answer = 0
 
    count = 0
 
    queue = deque()
 
    queue.append([x1,y1])
 
    answer += k[x1][y1]
 
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
 
    while queue:
 
        x,y = queue.popleft()
 
        k[x][y]=0
 
        if count == 3:            
            return answer
 
        max_x = 0
        max_y = 0
        max_answer = 0
 
        for i in range(4):            
 
            temp_x = x + dx[i]
            temp_y = y + dy[i]
 
            if 0<=temp_x<a and 0<=temp_y<b and k[temp_x][temp_y]>max_answer:
                max_x = temp_x
                max_y = temp_y
                max_answer = k[temp_x][temp_y]                                
 
 
        queue.append([max_x,max_y])
 
 
        answer += k[max_x][max_y]
        count+=1
 
 
 
a,b = list(map(int,sys.stdin.readline().split(" ")))
 
k = [ ]
 
 
for i in range(0,a):
    k.append(list(map(int,sys.stdin.readline().split(" "))))
 
 
 
 
answer = [ ]
 
 
for i in range(0,a):
    for j in range(0,b):
 
 
        k1 = copy.deepcopy(k)
 
        answer.append(bfs(i,j,k1,a,b))
 
max_answer = max(answer)
 
for i in range(0,a):
    for j in range(0,b-3):
 
        sums = 0
 
        if i==0:
            if k[i][j]+k[i][j+1]+k[i][j+2]+k[i+1][j+1] > max_answer:
                max_answer = k[i][j]+k[i][j+1]+k[i][j+2]+k[i+1][j+1]               
 
 
        elif i==a-1:
 
            if k[i][j]+k[i][j+1]+k[i][j+2]+k[i-1][j+1] > max_answer:
                max_answer = k[i][j]+k[i][j+1]+k[i][j+2]+k[i-1][j+1]         
 
 
 
        else:
            if k[i][j]+k[i][j+1]+k[i][j+2]+k[i+1][j+1] > max_answer:
                max_answer = k[i][j]+k[i][j+1]+k[i][j+2]+k[i+1][j+1]
 
            if k[i][j]+k[i][j+1]+k[i][j+2]+k[i-1][j+1] > max_answer:
                max_answer = k[i][j]+k[i][j+1]+k[i][j+2]+k[i-1][j+1]
 
 
 
 
 
 
print(max_answer)
 
 
 
 
 
 

s