[백준] 14500번 테트로미노 (by Python)

문제

문제를 읽으면 바로 모든 경우의 수를 시도해보는 브루트 포스 방식으로 풀어야 함을 알 수 있다. 그렇지만 고민이 되는 부분은 어떻게? 인 것 같다. 어떻게 회전도, 뒤집기도 가능한 테트로미노의 모양을 모두 테스트해볼 수 있을까? 더 나은 방법이 있을 거란 생각이 들었지만 일단 내가 시도해본 방법은 다음과 같다.

첫 번째 풀이

n, m = map(int, input().split())
array = []
answer = 0

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

for _ in range(n):
    array.append(list(map(int, input().split())))

for i in range(n):
    for j in range(m):
        for shape in shapes:
            temp = 0
            for s in shape:
                if 0 <= i + s[0] < n and 0 <= j + s[1] < m:
                    temp += array[i + s[0]][j + s[1]]
            answer = max(answer, temp)

print(answer)

그렇다. 모든 모양의 배치를 머릿속으로 떠올려서 리스트화...하는 것이다. shapes 리스트의 길이가 당신에게 놀라움을 안기지 않았기를 빈다. 실제로 시간 복잡도도 나쁘지 않아 정 해결방법이 떠오르지 않는다면 시도해볼만한 풀이인 것 같지만, 내 머리 복잡도와 정확성 측면에서 아쉬움이 남는다. 어떻게 내가 모든 모양들을 빠짐없이 체크했으며 다 올바르게 좌표를 찍었는지 확신할 수 있겠는가? 무언가 논리적으로 모양들을 생성해낼 수 있으리라는 막연한 생각이 들었고, 다른 분들의 풀이를 보며 감탄했다. 이거였구나. 해당 풀이들을 본 후 스스로 짜본 코드는 다음과 같다.

두 번째 풀이

import sys

input = sys.stdin.readline

def dfs(k, temp, r, c):
    global n, m
    global array
    global answer
    global visited
    global max_val

    steps = [(1, 0), (0, 1), (-1, 0), (0, -1)]

    if k == 4:
        answer = max(answer, temp)
        return
    if temp + (4 - k) * max_val < answer:
        return
    for step in steps:
        next_r = r + step[0]
        next_c = c + step[1]
        if 0 <= next_r < n and 0 <= next_c < m:
            if not visited[next_r][next_c]:
                visited[next_r][next_c] = True
                if k == 2:
                    # for ㅏ shape
                    dfs(k + 1, temp + array[next_r][next_c], r, c)
                dfs(k + 1, temp + array[next_r][next_c], next_r, next_c)
                visited[next_r][next_c] = False
    return


n, m = map(int, input().split())
array = []
answer = 0
visited = [[False for _ in range(m)] for _ in range(n)]

for _ in range(n):
    array.append(list(map(int, input().split())))

max_val = max(map(max, array))

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

print(answer)

핵심 아이디어는 DFS를 통해 모양들을 만드는 것이다. 테트로미노는 모두 정사각형 4개를 이어붙여 만든 도형들이므로 4번 움직인 경로는 모두 테트로미노 모양이 될 것이다.

그러나, 이러한 경로로 담아낼 수 없는 모양이 있다. 바로 'ㅏ' 모양이다. 이 모양을 만들기 위해 한 번 다음 목적지의 visited는 체크하되, 움직이지 않는 것이 필요하다.

그리고 여기까지 떠올렸다고 해도 훌륭한 것이라고 생각하지만, 우리가 사용하는 언어는 파이썬이기에 시간복잡도를 줄이기 위해 한 가지 트릭을 더 사용해야 한다. DFS로 모든 경우의 수를 시험해볼 수 있지만, 사실 겹치거나 필요없는 경우를 시도하게 될 때가 있다. 이러한 시도를 최소화하기 위해 전체 수들 중에서 최댓값 max_val을 구한 후, DFS 중에 남은 경로의 자취가 모두 최댓값이 나온다고 하더라도 현재의 답을 갱신할 수 없을 때, 그 search는 끝내도록 하는 것이다.

위의 아이디어를 모두 수행했을 때, 시간 내에 정확한 답을 찾아내는 코드를 비로소 작성됐을 것이다:)