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

문제

https://www.acmicpc.net/problem/14500

14500번: 테트로미노

 

풀이

[수정 전]

브루트포스 알고리즘을 사용해 풀었습니다.

tetrominos에 모든 테트로미노에 대해 왼쪽 위 인덱스(x, y)를 기준으로 더할 값을 저장합니다.

모든 테트로미노를 모든 위치에 대조해보며 더 높은 값을 계속해서 업데이트합니다.

[수정 후]

백트래킹을 사용해 풀었습니다.

오른쪽, 왼쪽, 아래로 뻗어가면서 테트로미노(4)가 완성되면 더 높은 값을 비교해 업데이트합니다.

L이 1인 경우 'ㅗ' 모양을 위해 다음 위치가 아닌 현재 위치에서 다시 뻗어가도록 해줍니다.

 

코드

파이썬

[수정 전] - 5888 ms

import sys

input = sys.stdin.readline

tetrominos = [
    [[(0, 1), (0, 2), (0, 3)], [(1, 0), (2, 0), (3, 0)]],
    [[(0, 1), (1, 0), (1, 1)]],
    [
        [(1, 0), (2, 0), (2, 1)],
        [(0, 1), (0, 2), (1, 0)],
        [(0, 1), (1, 1), (2, 1)],
        [(-1, 2), (0, 1), (0, 2)],
        [(-2, 1), (-1, 1), (0, 1)],
        [(1, 0), (1, 1), (1, 2)],
        [(0, 1), (1, 0), (2, 0)],
        [(0, 1), (0, 2), (1, 2)],
    ],
    [
        [(1, 0), (1, 1), (2, 1)],
        [(-1, 1), (-1, 2), (0, 1)],
        [(-1, 1), (0, 1), (1, 0)],
        [(0, 1), (1, 1), (1, 2)],
    ],
    [
        [(0, 1), (0, 2), (1, 1)],
        [(-1, 1), (0, 1), (1, 1)],
        [(-1, 1), (0, 1), (0, 2)],
        [(1, 0), (1, 1), (2, 0)],
    ],
]

answer = 0
N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]

for tetromino in tetrominos:
    for t in tetromino:
        for x in range(N):
            for y in range(M):
                if (
                    0 <= x + t[0][0]
                    and x + t[-1][0] < N
                    and 0 <= y + sorted(t, key=lambda x: x[1])[0][1]
                    and y + sorted(t, key=lambda x: x[1])[-1][1] < M
                ):
                    total = board[x][y]
                    for dx, dy in t:
                        nx = x + dx
                        ny = y + dy
                        total += board[nx][ny]
                    answer = max(answer, total)

print(answer)

[수정 후] - 766 ms

import sys

input = sys.stdin.readline

dx = [0, 1, 0]
dy = [1, 0, -1]

answer = 0
N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * M for _ in range(N)]


def DFS(x, y, total, L):
    global answer
    if L == 3:
        answer = max(answer, total)
    else:
        for i in range(3):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
                if L == 1:
                    visited[nx][ny] = True
                    DFS(x, y, total + board[nx][ny], L + 1)
                    visited[nx][ny] = False
                visited[nx][ny] = True
                DFS(nx, ny, total + board[nx][ny], L + 1)
                visited[nx][ny] = False


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

print(answer)