백준 14500 테트로미노

틀린 답

import sys
from collections import deque
input = sys.stdin.readline

n, m = list(map(int, input().rstrip().split()))
board = [list(map(int, input().rstrip().split())) for _ in range(n)]
maximum = -sys.maxsize
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs(node):
    q = deque([node])
    max_sum = -sys.maxsize
    while q:
        px, py, pd = q.popleft()
        if pd == 4:
            max_sum = max(max_sum, visited[px][py])
            continue
        for i in range(4):
            nx = px + dx[i]
            ny = py + dy[i]
            if (0 <= nx < n) and (0 <= ny < m) and (not visited[nx][ny]):
                visited[nx][ny] = visited[px][py] + board[nx][ny]
                q.append((nx, ny, pd + 1))
    return max_sum

for i in range(n):
    for j in range(m):
        visited = [[0] * m for _ in range(n)]
        visited[i][j] = board[i][j]
        maximum = max(maximum, bfs((i, j, 1)))
        if i < n - 2 and j < m - 1:
            maximum = max(maximum, board[i][j] + board[i + 1][j] + board[i + 1][j + 1] + board[i + 2][j])
        # ㅜ
        if i < n - 1 and j < m - 2:
            maximum = max(maximum, board[i][j] + board[i][j + 1] + board[i][j + 2] + board[i + 1][j + 1])
        # ㅗ
        if i >= 1 and j < m - 2:
            maximum = max(maximum, board[i][j] + board[i - 1][j + 1] + board[i][j + 1] + board[i][j + 2])
        # ㅓ
        if 1 <= i < n - 1 and j < m - 1:
            maximum = max(maximum, board[i][j] + board[i - 1][j + 1] + board[i][j + 1] + board[i + 1][j + 1])

print(maximum)

처음에 간단한 bfs 문제라고 생각했으나... ㅗ 모양의 블럭 때문에 bfs 커스텀하다가 1시간정도 날리고... 어찌어찌 해결해서 제출했으나 시간초과..
결국 dfs로 바꿨다 (저 블럭을 출제자에게 주고싶다)

답

import sys
input = sys.stdin.readline

n, m = list(map(int, input().rstrip().split()))
board = [list(map(int, input().rstrip().split())) for _ in range(n)]
max_val = max(map(max, board))
maximum = -sys.maxsize
visited = [[False] * m for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bt(x, y, depth, sum):
    global maximum
    if sum + max_val * (4 - depth) <= maximum:
        return
    if depth == 4:
        maximum = max(maximum, sum)
        return
    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]):
            if depth == 2:
                visited[nx][ny] = True
                bt(x, y, depth + 1, sum + board[nx][ny])
                visited[nx][ny] = False
            visited[nx][ny] = True
            bt(nx, ny, depth + 1, sum + board[nx][ny])
            visited[nx][ny] = False

for i in range(n):
    for j in range(m):
        visited[i][j] = True
        bt(i, j, 1, board[i][j])
        visited[i][j] = False

print(maximum)

눈물이 찔 끔 날 정도로. .. 많이 틀렸다... 검색해서 나온답을 거의 클론코딩했다........
약간 속이 거북하다 지금
한 번 더 풀어봐야지...