[Baekjoon]14500. 테트로미노

문제를 보자마자 테트로미노 모양대로 좌표 틀을 만들어서 도장 찍듯이 찍어볼까?라고 생각했음

테트로미노 모양대로 이동 방향이 적힌 딕셔너리를 일일이 만들다가

생각해 보니 dfs로 풀되, 이동 횟수를 3번으로 고정시키면 훨씬 수월할 것 같았음

다만, ㅗ모양의 테트로미노는 dfs가 아닌 반복문을 사용함

 

# ㅗ모양을 제외한 경로 탐색
def f(x, y, n, s):
    """
    x, y: 현재 좌표
    n: 경로 탐색 횟수
    s: 경로 탐색한 좌표값의 합
    """
    global path
    global max_val
    if [x, y] not in path:
        path.append([x, y])
        s += arr[x][y]

    delta = [[-1, 0], [1, 0], [0, 1], [0, -1]]

    # 4칸 채우면 최댓값 계산
    if n == 3:
        max_val = max(max_val, s)
        return
        
    # backtracking
    if max_val - s >= 1000 * (3 - n):
        return

    for i in range(4):
        ni = x + delta[i][0]
        nj = y + delta[i][1]
        if 0 <= ni < N and 0 <= nj < M and [ni, nj] not in path:
            f(ni, nj, n+1, s)
            path.pop()

# ㅗ모양 경로 탐색
def f2(x, y):
    """
    x, y: 현재 좌표
    """
    global max_val
    delta = [[-1, 0], [1, 0], [0, 1], [0, -1]]
    for i in range(4):
        path = [[x, y]]
        s = arr[x][y]
        d = i
        n = 0
        while True:
            ni = x + delta[d][0]
            nj = y + delta[d][1]
            if 0 <= ni < N and 0 <= nj < M and [ni, nj] not in path:
                path.append([ni, nj])
                s += arr[ni][nj]
                d = (d + 1) % 4
                n += 1
            else:
                break

            # 4칸 채우면 최대값 계산
            if n == 3:
                max_val = max(max_val, s)
                break
                
            # backtracking
            if max_val - s >= 1000 * (3 - n):
                break

import sys
input = sys.stdin.readline

N, M = map(int, input().split())  # 4<=N,M<=500
arr = [list(map(int, input().split())) for _ in range(N)]
max_val = 0

for i in range(N):
    for j in range(M):
        path = []
        f(i, j, 0, 0)
        f2(i, j)

print(max_val)

 

시간 초과 원인 → 백트래킹을 하지 않음

dfs는 항상 백트래킹의 유무 및 방식이 시간 초과를 결정하는 것 같음

주어진 행렬 안의 수가 1000을 넘지 않으므로, `max_val - s >= 1000 * (3 - n)`일 경우 return or break 하도록 설계함

max_val: 현재까지 구한 최댓값

s: 경로 탐색 중 더한 값

n: 탐색한 횟수

 

예전에 다른 dfs문제에서 경로와 방향을 string으로 저장해서 key처럼 쓰는 방식이 있었는데, list 활용하는 방식이 더 빨랐음