[BOJ] 14500. 테트로미노

📌 문제 제목

문제 링크: BOJ 14500

 

---

🗒️ 문제 설명

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

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

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

크기가 NxM인 종이 위에 테트로미노 하나를 놓으려고 한다.

종이는 1x1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여있다.

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

시간 제한: 2초

메모리 제한: 512MB

세로 크기 N, 가로 크기 M에 대해 4 <= N, M <= 500

---

💡 문제 해결 아이디어

• 아래의 모양을 제외한 테트로미노들은 DFS + backtracking을 사용하여 구현할 수 있다. 
  • backtracking에 direction을 추가한 로직 사용

• ㅗ 모양은 따로 로직 필요
  • 모양 좌표 정의

---

⌛️ 시간 복잡도

• O(NM)

---

✅ 최종 코드

import sys
input = sys.stdin.readline

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

visited = [[False] * M for _ in range(N)]
mx = 0
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
answer = [0] * 4


def backtrack(x, y, k):
    global mx
    answer[k] = graph[x][y]
    if k == 3:
        total = sum(answer)
        mx = max(mx, total)
        return
    for dx, dy in direction:
        nx, ny = x + dx, y + dy
        if not (0 <= nx < N and 0 <= ny < M):
            continue
        if not visited[nx][ny]:
            visited[nx][ny] = True
            backtrack(nx, ny, k+1)
            visited[nx][ny] = False


# ㅗ 모양
shapes = [
    [(0, 0), (-1, 0), (1, 0), (0, 1)],
    [(0, 0), (-1, 0), (1, 0), (0, -1)],
    [(0, 0), (0, -1), (0, 1), (1, 0)],
    [(0, 0), (0, -1), (0, 1), (-1, 0)]
]


def solution(x, y):
    global mx
    for shape in shapes:
        total = 0
        for dx, dy in shape:
            nx, ny = x + dx, y + dy
            if not (0 <= nx < N and 0 <= ny < M):
                break
            total += graph[nx][ny]
        mx = max(mx, total)


for i in range(N):
    for j in range(M):
        visited[i][j] = True
        backtrack(i, j, 0)
        visited[i][j] = False

        solution(i, j)  # ㅗ 모양 찾기


print(mx)

import sys
input = sys.stdin.readline

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

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

mx = -1
max_val = max(map(max, graph))  # 가장 큰 수


def dfs(x, y, k, total, visited):
    global mx

    # 지금까지의 누적합 + 남은 칸 수 * 가장 큰 수를 해도 mx보다 작으면 탐색할 필요가 없음.
    if total + max_val * (4 - k) <= mx:
        return

    if k == 4:
        mx = max(mx, total)
        return

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

        if not (0 <= nx < N and 0 <= ny < M):
            continue
        else:
            if not visited[nx][ny]:
                visited[nx][ny] = True
                dfs(nx, ny, k+1, total+graph[nx][ny], visited)
                if k == 2: # 이걸로 ㅗ 모양도 찾을 수 있음.
                    dfs(x, y, k + 1, total+graph[nx][ny], visited)
                visited[nx][ny] = False


visited = [[False] * M for _ in range(N)]

for i in range(N):
    for j in range(M):
        visited[i][j] = True
        dfs(i, j, 1, graph[i][j], visited)
        visited[i][j] = False

print(mx)

---

https://jominseoo.tistory.com/96 이 분이 정리를 엄청 잘 해놓으심