BOJ #14500 테트로미노

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

문제 14500. 테트로미노

문제 풀이 - 1

각 블록의 배치를 하나씩 전부 고려하면 한 지점 당 19가지가 나온다. N과 M이 500이고 전체 가지수가 19이면 5,000,000의 연산으로 나름? 할만하다. 거기에 각 4개 블록에 대한 범위 체크까지 고려하면 최대 총 1천만번의 연산으로 아슬아슬하다.

python 코드 - 1

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

N, M = map(int, input().split())
graph = []
check = [[0 for _ in range(M)] for _ in range(N)]
for _ in range(N):
    graph.append(list(map(int, input().split())))

block = [
    [[0, 0], [0, 1], [0, 2], [0, 3]],
    [[0, 0], [1, 0], [2, 0], [3, 0]],

    [[0, 0], [0, 1], [1, 0], [1, 1]],

    [[0, 0], [1, 0], [2, 0], [2, 1]],
    [[0, 0], [1, 0], [0, 1], [0, 2]],
    [[0, 0], [0, 1], [1, 1], [2, 1]],
    [[0, 0], [0, 1], [0, 2], [-1, 2]],
    [[0, 0], [0, 1], [1, 0], [2, 0]],
    [[0, 0], [0, 1], [0, 2], [1, 2]],
    [[0, 0], [1, 0], [2, 0], [2, -1]],
    [[0, 0], [-1, 0], [0, 1], [0, 2]],

    [[0, 0], [1, 0], [1, 1], [2, 1]],
    [[0, 0], [-1, 1], [0, 1], [-1, 2]],
    [[0, 0], [0, 1], [1, 1], [1, 2]],
    [[0, 0], [1, 0], [1, -1], [2, -1]],

    [[0, 0], [1, -1], [1, 0], [1, 1]],
    [[0, 0], [1, 0], [1, 1], [2, 0]],
    [[0, 0], [0, 1], [0, 2], [1, 1]],
    [[0, 0], [1, 0], [1, -1], [2, 0]]
]

def cal(y, x):
    result = 0 # 해당 지점에서 발생할 수 있는 최종값
    for i in range(len(block)): # 각 블록의 유형에 대해
        s = 0 # 산출값 초기화
        v_list = [[y + ny, x + nx] for ny, nx in block[i]]
        for v in v_list: # 블록의 각 지점에 대해
            if 0 <= v[0] < N and 0 <= v[1] < M: # 범위 내라면
                s += graph[v[0]][v[1]] # 값 반영
            else: # 범위 밖이면 더 볼 필요 없음
                break
        result = max(result, s) # 각 블록에 대해 최대값 점검
    return result # 최종값 반환

sol = 0
for i in range(N):
    for j in range(M):
        sol = max(sol, cal(i, j))
print(sol)

문제풀이 - 2

이렇게 풀면 전체 풀이 시간이 python3 기준 약 7초 정도가 나온다. 그러나 뭔가 마음에 들지 않는다. 너무 말 그대로 브루트포스 방식의 소요시간이기 떄문이다. 그렇다면 DFS를 사용한 그래프 탐색으로 백트래킹 기법을 사용할 수 있지 않을까 싶다. 다만, 주의할 점으로 'ㅏ'나 'ㅓ' 모양의 블록은 DFS를 진행할 때 조금 주의를 기울여야 한다. 왜냐하면 2번째 탐색 지점에서 두 갈래의 블록을 모두 반영해야 하는데 DFS 특성 상 한 지점에 대해 탐색을 마치고 다음 지점으로 넘어가기 때문이다. 이를 해결하기 위해 깊이 2의 위치에서 다른 지점에 대해 탐색을 진행하고 탐색 위치를 변경하지 않은 채로 다음 탐색 지점을 골라 탐색을 진행하면 한 탐색 위치에서 두 개의 블록을 반영할 수 있다.

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [[0 for _ in range(M)] for _ in range(N)]
check = [[0 for _ in range(M)] for _ in range(N)]
max_val = 0
for i in range(N):
    row = list(map(int, input().split()))
    for j, r in enumerate(row):
        graph[i][j] = r
        if max_val < r:
            max_val = r

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

sol = 0

def dfs(y, x, depth, s):
    global sol
    if depth == 4:
        sol = max(s, sol)
        return False
    if s + (4 - depth) * max_val <= sol:
        return False # 나머지 깊이 값이 모두 최대값이라도 갱신 불가능한 경우
    for d in range(4):
        ny, nx = y + dy[d], x + dx[d]
        if 0 <= ny < N and 0 <= nx < M and check[ny][nx] == 0:
            if depth == 2: # 'ㅏ', 'ㅓ' 모양의 가운데 지점인 경우 (깊이 2)
                check[ny][nx] = 1 # 깊이 3의 지점 방문 처리
                # 깊이 2 지점에서 다시 탐색해서 깊이 4 지점 탐색
                dfs(y, x, depth + 1, s + graph[ny][nx])
                check[ny][nx] = 0
            check[ny][nx] = 1
            dfs(ny, nx, depth + 1, s + graph[ny][nx])
            check[ny][nx] = 0
    return False

for i in range(N):
    for j in range(M):
        check[i][j] = 1
        dfs(i, j, 1, graph[i][j])
        check[i][j] = 0
print(sol)