[백준] 14500번 테트로미노 ★★★

💡문제접근

• 어떤 결과를 요구하는지 알고는 있었지만 이걸 코드로 옮기는 과정의 시작부터 막막해서 결국 어떤 방식으로 접근을 할 수 있는지 구글링을 해보았다.(코드는 보지 않음)
• ㅗ, ㅜ, ㅏ, ㅓ 모양의 블록은 DFS를 이용해서 탐색을 해야하고 그 외 모양의 블록들은 DFS를 이용하지 않아도 된다는 점이 가장 핵심이었다.

💡코드(메모리 : 38008KB, 시간 : 5376ms)

import sys
input = sys.stdin.readline

# ㅏ, ㅓ, ㅗ, ㅜ 모양의 블록 DFS탐색
def DFS(x, y, idx, total):
    global ans
    if idx == 3:
        ans = max(total, ans)
    else:
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if visited[nx][ny] == False:
                    visited[nx][ny] = True
                    DFS(nx, ny, idx+1, total+board[nx][ny])
                    visited[nx][ny] = False

# 나머지 모양의 블록들
def block(x, y, total):
    global ans
    block_count = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < M:
            block_count += 1
            total += board[nx][ny]

    if block_count == 3:
        ans = max(ans, total)

    if block_count == 4:
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            total -= board[nx][ny]
            if total > ans:
                ans = total
            total += board[nx][ny]

N, M = map(int, input().strip().split())
board = [list(map(int, input().strip().split())) for _ in range(N)]
visited = [[False] * M for _ in range(N)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
ans = 0

for i in range(N):
    for j in range(M):
        visited[i][j] = True
        DFS(i, j, 0, board[i][j])
        block(i, j, board[i][j])
        visited[i][j] = False
print(ans)

💡소요시간 : 3h