[Python] 백준/BOJ 14500번: 테트로미노 (Gold 4)

💻 Problem

문제 보러 가기

 

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

• 정사각형은 서로 겹치면 안 된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

• 4 ≤ N, M ≤ 500

 

💡 Approach

5개의 테트로미노 중 'ㅜ' 모양을 제외하고는 4방향 탐색으로 탐색이 가능하다.

다만, 'ㅜ' 모양의 경우 탐색을 하다가 한 칸 뒤로 가야 하기 때문에 예외 처리를 해줘야 한다.

예제

 

4방향 탐색이라 하면 난 자연스럽게 bfs, dfs 중 bfs를 선택하게 된다.. << 훨씬 편해서

무지성 bfs ㄱㄱ 좀 멈춰야 될 거 같다... ㅋㅋ

저번에도 문제 풀 때 bfs로 풀다가 bfs로는 방문 배열을 매번 초기화해줘야 하는데 dfs는 재귀 전후로 방문 처리 관리해 주면 돼서 dfs로 다시 짰었다. 

이번에도 마찬가지.. bfs로 풀다가 시간초과 떠서 dfs로 다시 짰다..

 

모든 좌표를 시작점으로 삼아 시작점에서 4개의 블록을 가지고 테트로미노를 완성하도록 탐색하면 된다.

 

'ㅜ' 모양을 제외한 테트로미노는 일반적인 dfs여서 쉽게 짰는데 이제 'ㅜ' 모양의 테트로미노를 어떻게 처리할 것인지가 난관이었다.

'ㅜ' 모양의 테트로미노는 그냥 특수 상황이라고 치고 슬라이싱이나 델타 좌표를 통해 'ㅗ', 'ㅜ', 'ㅓ', 'ㅏ' 4개만 직접 구했다.

 

✏️ Solution

import sys
input = sys.stdin.readline

# ㅜ 모양의 테트로미노 탐색하는 함수
def find_t(y, x):
    max_total = 0
    for case in t_d:
        total = 0
        # ㅜ, ㅗ, ㅓ, ㅏ 탐색
        for c in case:
            ny = y + c[0]
            nx = x + c[1]

            if not (0 <= ny < N) or not (0 <= nx < M):
                break

            total += board[ny][nx]
        max_total = max(max_total, total)
    return max_total

# ㅜ를 제외한 4개의 테트로미노를 탐색하는 함수
def dfs(y, x, cnt, total):
    global max_total
    # 블록 4개가 연결되면 테트로미노 완성
    if cnt == 4:
        max_total = max(max_total, total)
        return
    
    # 상하좌우 탐색
    for dx, dy in d:
        ny = y + dy
        nx = x + dx

        if (0 <= ny < N) and (0 <= nx < M) and not visited[ny][nx]:
            visited[ny][nx] = True
            dfs(ny, nx, cnt + 1, total + board[ny][nx])
            visited[ny][nx] = False

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

d = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 상하좌우
t_d = [[(0, 0), (0, 1), (0, 2), (1, 1)],
       [(0, 0), (0, 1), (0, 2), (-1, 1)],
       [(0, 0), (1, -1), (1, 0), (2, 0)],
       [(0, 0), (1, 0), (1, 1), (2, 0)]] # ㅗ, ㅜ, ㅓ, ㅏ

# 모든 좌표를 시작점으로 탐색
for i in range(N):
    for j in range(M):
        visited[i][j] = True
        # ㅜ 모양 테트로미노 찾기
        max_total = max(max_total, find_t(i, j))
        # ㅜ를 제외한 나머지 테트로미노 찾기
        dfs(i, j, 1, board[i][j])
        visited[i][j] = False

print(max_total)

위 접근대로 푼 코드이다.

하지만 다른 사람들 코드를 보니 델타 좌표도, 슬라이싱도 없이 풀었길래 나도 참고해서 최적화해 봤다.

 

import sys
input = sys.stdin.readline

def dfs(y, x, cnt, total):
    global max_total
    # 남은 블록의 값이 최댓값이어도 max_total을 넘지 못하면 종료
    if total + max_val * (4 - cnt) <= max_total:
        return

    # 블록 4개가 연결되면 테트로미노 완성
    if cnt == 4:
        max_total = max(max_total, total)
        return

    for dx, dy in d:
        ny = y + dy
        nx = x + dx

        if (0 <= ny < N) and (0 <= nx < M) and not visited[ny][nx]:
            visited[ny][nx] = True

            # ㅜ 모양 테트로미노 처리
            if cnt == 2:    
                dfs(y, x, cnt + 1, total + board[ny][nx])

            dfs(ny, nx, cnt + 1, total + board[ny][nx])
            visited[ny][nx] = False

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

d = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 상하좌우

# 모든 좌표를 시작점으로 탐색
for i in range(N):
    for j in range(M):
        visited[i][j] = True
        dfs(i, j, 1, board[i][j])
        visited[i][j] = False

print(max_total)

cnt가 2일 때는 현재 위치에서 블록을 2개 찾도록 했다.

 

블록 안에 적힌 숫자는 cnt이다. (현재까지 연결한 블록 수)

cnt가 2일 때, 현재 좌표는 (y, x)이고, 다음 탐색할 좌표는 (ny, nx)일 것이다.

(ny, nx)의 위치는 현재 블록의 왼쪽 블록이라고 하겠다.

 

먼저 왼쪽 블록을 방문 처리한다.

그 후, 블록을 하나 더 연결하기 위해 (y, x)를 탐색한다.

위쪽과 왼쪽은 이미 방문했으므로, 오른쪽과 아래쪽으로만 탐색이 가능하다.

이 시점에서 오른쪽을 탐색해 이어 붙이면 'ㅗ'자 모양이, 아래쪽을 탐색하면 'ㅓ'자 모양의 테트로미노가 만들어진다.

 

오른쪽을 탐색한 경우, 오른쪽에 4번째 블록이 연결될 것이다.

이러면 'ㅗ' 테트로미노가 완성된다.

 

추가로 dfs 탐색 시작에 앞으로 연결할 블록들의 값이 다 보드의 최댓값이어도 max_total을 넘지 못하면 탐색을 하지 않도록 가지치기를 했다.

가지치기를 하지 않았을 때는 pypy3 기준 1024ms였는데, 가지치기를 추가하니 156ms가 되었다.

가지치기의 중요성..