보드가 주어졌을 때, 4칸짜리 테트로미노(대각선 없이 연결된 모양)중 합이 가장 큰 경우를 찾는 문제다.
고려했던 사항은 다음과 같다.
풀이 과정은 다음과 같다.
이 문제는 정말 애를 먹었다... 처음에는 dfs로 모든 경우를 찾으면서 이미 돌아본 블럭 모음(테트로미노)는 뛰어넘는 식으로 하려 했지만 dfs의 경우 ㅗ모양을 빠뜨려야 했다. 그래서, bfs로 접근하고 처음에는 브루트 포스로 모든 경우를 계산했지만 메모리/시간 초과가 나와서 최대 값을 가지는 블록만 붙이는 식으로 변경했다. 아직은 경험이 부족해서 시간도 오래걸리고, 이상한 방향으로 풀이를 잡는 경우가 많은것 같다. 연습하자... 백준에서 풀이를 보니 대부분 모든 경우의 수(블록 offset)을 만든 후에 순회하는 식으로 짰다. 테스트 당시에는 오히려 풀이 시간을 단축할 수 있겠다는 생각을 했다.
import sys
def bfs():
global answer
if len(block) == 4:
blockSum = sum(map(lambda a: board[a[0]][a[1]], block))
answer = max(answer, blockSum)
return False
blockSum = 0
nearBlocks = []
for bi, bj in block:
if bi - 1 >= 0 and (bi - 1, bj) not in block:
nearBlocks.append((board[bi - 1][bj], bi - 1, bj))
if bi + 1 < n and (bi + 1, bj) not in block:
nearBlocks.append((board[bi + 1][bj], bi + 1, bj))
if bj - 1 >= 0 and (bi, bj - 1) not in block:
nearBlocks.append((board[bi][bj - 1], bi, bj - 1))
if bj + 1 < m and (bi, bj + 1) not in block:
nearBlocks.append((board[bi][bj + 1], bi, bj + 1))
block.append(tuple(max(nearBlocks, key = lambda a: a[0])[1:]))
return True
n, m = map(int, sys.stdin.readline().strip().split(' '))
board = [[] for _ in range(n)]
for i in range(n):
line = map(int, sys.stdin.readline().strip().split(' '))
for l in line:
board[i].append(l)
answer = 0
for i in range(n):
for j in range(m):
block = [(i, j)]
while(bfs()):
pass
print(answer)