백준(BOJ) 14500 테트로미노(Python)

문제 내용

 

브루트포스 문제.

블록 모양을 구현하기 위해 DFS를 사용했다. 길이가 4일 때까지 DFS를 하고, 길이가 4인 경우에는 이때까지 블록에 적힌 수의 합을 ans에 갱신한다. 그러나 위와 같이 DFS를 하면 그림의 보라색 블록을 커버할 수 없다. 따라서 보라색 모양은 따로 고려해서 DFS를 진행했다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
from itertools import combinations
from itertools import permutations
import bisect
input=sys.stdin.readline
#sys.setrecursionlimit(100000000)


def func(t,x,y,k,z):
    global ans,n,m
    if t==4:
        ans=max(ans,k)
        return
    if t==2:
        for i in range(-1,2,2):
            nx=x+dx[(i+z)%4]
            ny=y+dy[(i+z)%4]
            if 0<=nx<n and 0<=ny<m and 0<=x+dx[z]<n and 0<=y+dy[z]<m and not visited[nx][ny] and not visited[x+dx[z]][y+dy[z]]:
                ans=max(ans,k+L[nx][ny]+L[x+dx[z]][y+dy[z]])
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if 0<=nx<n and 0<=ny<m and not visited[nx][ny]:
            visited[nx][ny]=1
            func(t+1,nx,ny,k+L[nx][ny],i)
            visited[nx][ny]=0
    
n,m=map(int,input().split())
L=[list(map(int,input().split())) for i in range(n)]
dx=[0,1,0,-1]
dy=[1,0,-1,0]
visited=[[0]*m for i in range(n)]
ans=0
for i in range(n):
    for j in range(m):
        visited[i][j]=1
        func(1,i,j,L[i][j],-1)
        visited[i][j]=0
print(ans)