[BOJ] 테트리미노 (14500, G4)

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

우선, 어느 모양이 최대값이 될지 모른다. bfs는 이런 류에서 직전의 위치로 돌아가 올바르게 탐사할 수 없다. 아니, 이전의 길을 올바르게 기억할 수가 없기 때문에 bfs는 불가. 기본적으로는 dfs를 해야 한다.

문제는, dfs는 깊이 탐색이기 때문에 그것이 불가능한 모양이 존재한다. 그것은 바로. T 모양의 테트리미노.
이것의 경우는 별도로 예외 처리를 해 줘야 한다.

dfs로 이전에 갔던 곳은 가지 않고, 딱 4칸 파게 진행을 해야한다. 어느 시작칸에서 최대가 날지 모르니까 모든 칸을 다 브루트 포스로 시도해 봐야 하고 그렇게 코드를 짜면 다음과 같다.

import sys
input = sys.stdin.readline
tetra_map = []
rows, cols = map(int, input().split())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for _ in range(rows):
    cur_row = list(map(int, input().split()))
    tetra_map.append(cur_row)

max_sum = 0
def tetra_max(cur_x, cur_y, level, cur_sum):
    global max_sum
    if level == 4:
        if max_sum < cur_sum:
            max_sum = cur_sum
        return
    else:
        for k in range(4):
            new_x = cur_x + dx[k]
            new_y = cur_y + dy[k]
            if 0 <= new_x < rows and 0 <= new_y < cols:
                if not visited[new_x][new_y]:
                    visited[new_x][new_y] = True
                    tetra_max(new_x, new_y, level + 1,
                              cur_sum + tetra_map[new_x][new_y])
                    visited[new_x][new_y] = False
# DFS로는 ㅗ 모양 불가./회전 고려하기.
def t_sum(i, j):
    global max_sum
    # ㅗ 방향 체크
    if i-1 >= 0 and j+2 <= cols-1:
        cur_sum = tetra_map[i][j] + tetra_map[i][j+1] + tetra_map[i-1][j+1] + tetra_map[i][j+2]
        if cur_sum >= max_sum:
            max_sum = cur_sum
    # ㅜ 방향 체크        
    if i+1 <= rows-1 and j+2 <= cols-1:
        cur_sum = tetra_map[i][j] + tetra_map[i][j+1] + tetra_map[i+1][j+1] + tetra_map[i][j+2]
        if cur_sum >= max_sum:
            max_sum = cur_sum
    # ㅏ 방향 체크        
    if i+2 <= rows-1 and j+1 <= cols-1:
        cur_sum = tetra_map[i][j] + tetra_map[i+1][j] + tetra_map[i+1][j+1] + tetra_map[i+2][j]
        if cur_sum >= max_sum:
            max_sum = cur_sum
    # ㅓ 방향 체크        
    if i+2 <= rows-1 and j-1 >= 0:
        cur_sum = tetra_map[i][j] + tetra_map[i+1][j] + tetra_map[i+1][j-1] + tetra_map[i+2][j]
        if cur_sum >= max_sum:
            max_sum = cur_sum

for i in range(rows):
    for j in range(cols):
        visited = [[False for _ in range(cols)] for _ in range(rows)]
        visited[i][j] = True
        tetra_max(i, j, 1, tetra_map[i][j])
        t_sum(i, j)

print(max_sum)

문제는 이렇게 하면, 시간 초과가 발생한다. 그 이유를 생각해보면 visited 처리에서 되게 오래 시간을 잡아 먹는 것으로 보인다. dfs를 제대로 하려면, 이전 칸으로 돌아가서는 안되는데...

테트리미노의 모양을 다시 생각하면 현재 칸에서 다음칸이 될 수 있는 후보 4칸이 이전 칸과 겹치면 안 된다.
그런데, 그 이전칸은 맨 처음칸이 될 수 없다! 전전 칸하고만 안 겹치면 된다.  이는 처음 시작점에서 3번째 칸을 볼 때에도 유효하다.

즉 전전것하고만 비교하게 하면 된다. 즉 이전 좌표와 현재 좌표 두 개만 기억해두고 함수로 넘기면 충분하다.

import sys
input = sys.stdin.readline
tetra_map = []
rows, cols = map(int, input().split())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for _ in range(rows):
    cur_row = list(map(int, input().split()))
    tetra_map.append(cur_row)

max_sum = 0
def tetra_max(cur_x, cur_y, prev_x, prev_y, level, cur_sum):
    global max_sum
    if level == 4:
        if max_sum < cur_sum:
            max_sum = cur_sum
        return
    else:
        for k in range(4):
            new_x = cur_x + dx[k]
            new_y = cur_y + dy[k]
            if 0 <= new_x < rows and 0 <= new_y < cols:
                if new_x != prev_x or new_y != prev_y:
                    tetra_max(new_x, new_y, cur_x, cur_y, level + 1,
                              cur_sum + tetra_map[new_x][new_y])
# DFS로는 ㅗ 모양 불가./회전 고려하기.
def t_sum(i, j):
    global max_sum
    # ㅗ 방향 체크
    if i-1 >= 0 and j+2 <= cols-1:
        cur_sum = tetra_map[i][j] + tetra_map[i][j+1] + tetra_map[i-1][j+1] + tetra_map[i][j+2]
        if cur_sum >= max_sum:
            max_sum = cur_sum
    # ㅜ 방향 체크        
    if i+1 <= rows-1 and j+2 <= cols-1:
        cur_sum = tetra_map[i][j] + tetra_map[i][j+1] + tetra_map[i+1][j+1] + tetra_map[i][j+2]
        if cur_sum >= max_sum:
            max_sum = cur_sum
    # ㅏ 방향 체크        
    if i+2 <= rows-1 and j+1 <= cols-1:
        cur_sum = tetra_map[i][j] + tetra_map[i+1][j] + tetra_map[i+1][j+1] + tetra_map[i+2][j]
        if cur_sum >= max_sum:
            max_sum = cur_sum
    # ㅓ 방향 체크        
    if i+2 <= rows-1 and j-1 >= 0:
        cur_sum = tetra_map[i][j] + tetra_map[i+1][j] + tetra_map[i+1][j-1] + tetra_map[i+2][j]
        if cur_sum >= max_sum:
            max_sum = cur_sum

for i in range(rows):
    for j in range(cols):
        tetra_max(i, j, -1, -1, 1, tetra_map[i][j])
        t_sum(i, j)

print(max_sum)

tetra_max의 함수 호출 부분과 중복 처리 부분을 주의해서 비교해보자. 이 문제에선 4칸이기 때문에 특수성으로 가능하다.
아, 이래도 T자는 불가능하다. 예외처리해주자.