[파이썬(Python)] 백준 14500번 테트로미노

 

 

문제

문제 바로 가기

---

📌 문제

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.
1. 정사각형은 서로 겹치면 안 된다.
2. 도형은 모두 연결되어 있어야 한다.
3. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다. 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오. 테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

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

입력

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)
둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

출력

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

 

 

 

 

 

 

 

 

 

 

📝 아이디어

 

 

문제 분석

 

이 문제는 크기가 $N \times M$인 격자에서 테트로미노를 배치하여 해당 칸에 적힌 숫자의 합이 최대가 되는 값을 찾는 문제입니다. 

 

 

 

 

 

 

 

아이디어

 

 

1. 테트로미노 유형

 

테트로미노는 4개의 정사각형이 변을 맞대고 연결된 도형이며, 회전 및 대칭 변환을 포함한 모든 경우를 고려해야 합니다. 기본적으로 5가지 형태로 분류되며, 회전 및 대칭을 포함하면 총 19가지 변형이 존재합니다. 

 

 

• 막대형: 4개의 정사각형이 일직선으로 배치된 형태 → 가로와 세로 2가지 변형 존재

 

 

 

 

• 정사각형: 4개의 정사각형이 2 x 2 크기의 정사각형으로 배치된 형태 → 회전이나 대칭을 적용해도 동일하므로 1가지 형태만 존재

 

 

 

 

• 번개형: Z 또는 S 모양으로 배치된 형태  →  회전 시 4가지 변형 가능

 

 

 

 

• L자형: L 또는 ㄴ 모양으로 배치된 형태  → 회전 및 대칭을 포함하여 8가지 변형 존재

 

 

 

 

• T자형: 중심을 기준으로 4개의 정사각형이 T자형으로 배치된 형태  → 회전하여 4가지 변형 가능

 

 

 

 

 

 

2. 탐색 전략: 완전 탐색

 

테트로미노를 배치하여 최댓값을 찾기 위해 완전 탐색(Brute Force) 방식을 사용합니다. 즉, 격자의 모든 위치에서 테트로미노의 19가지 변형을 배치해보고 가능한 최댓값을 찾는 방식입니다. 

 

• 격자의 모든 칸 (i, j)를 시작점으로 설정합니다.
• 테트로미노의 19가지 변형을 미리 정의하여 모든 경우를 시뮬레이션합니다.
• 각 테트로미노를 (i, j) 위치에서 배치할 수 있는지 확인하고 배치가 가능하면 값의 합을 계산합니다.
• 모든 가능한 경우 중 최댓값을 갱신합니다.

 

 

 

 

 

3. 테트로미노 배치 검증

 

테트로미노를 배치할 때 격자를 벗어나는지 확인해야 합니다.

 

• 기준점 (i, j)를 설정합니다.
• 테트로미노의 상대 좌표를 더해 새로운 위치 (ni, nj) 계산합니다.
• 만약 (ni, nj)가 격자 범위를 벗어나면 무효 처리합니다.
• 유효한 경우, 4칸의 값 합산하여 최댓값을 갱신합니다.

 

 

 

 

 

4. 시간 복잡도 분석

 

각 위치에서 19가지 테트로미노 모양을 배치해야 하므로 시간 복잡도는 다음과 같습니다.

 

$$O(NM \times 19 \times 4) \sim O(76MN)$$

 

$N, M \leq 500$ 이므로, 최악의 경우 $500 \times 500 = 250,000$개의 위치에서 탐색합니다. 

 

 

 

 

 

 

 

 

 

 

👩‍💻 나의 답안

tets = [
    # 1. 막대형
    [(0,1), (0,2), (0,3)], [(1,0), (2,0), (3,0)], 

    # 2. 정사각형
    [(0,1), (1,0), (1,1)],

    # 3. L자형
    [(1,0), (1,1), (2,1)], [(0,-1), (1,-1), (1,-2)],
    [(1,0), (1,-1), (2,-1)], [(0,1), (1,1), (1,2)],
    [(1,0), (2,0), (2,1)], [(0,1), (0,2), (1,0)], 
    [(0,1), (1,1), (2,1)], [(0,1), (0,2), (-1,2)],
    [(1,0), (2,0), (2,-1)], [(0,1), (0,2), (1,2)], 
    [(1,0), (2,0), (0,1)], [(1,0), (1,1), (1,2)],

    # 4. 번개형 (Z, S)
    [(1,0), (1,1), (2,0)], [(0,-1), (1,0), (0,1)], 
    [(0,1), (-1,1), (1,1)], [(1,0), (1,-1), (1,1)]
]    

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

# 최댓값 저장
ans = 0

# 모든 위치에서 테트로미노 배치 시도
for i in range(n):
    for j in range(m):
        for tet in tets:
            temp = arr[i][j]  # 시작점 값 포함
            valid = True  # 유효한 모양인지 체크

            for di, dj in tet:
                ni, nj = i + di, j + dj
                if 0 <= ni < n and 0 <= nj < m:
                    temp += arr[ni][nj]
                else:
                    valid = False  # 범위를 벗어나면 해당 모양 무효
                    break
            
            if valid:
                ans = max(ans, temp)

# 결과 출력
print(ans)