[BJ14500] 테트로미노

🚩 문제 설명

https://www.acmicpc.net/problem/14500

14500번: 테트로미노

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

www.acmicpc.net

⏱️ 시간 복잡도
▪ 도형의 총 개수를 K 이라고 하자.
▪ O(KNM) 에 해당한다.

◾ 테트로미노가 놓인 종이의 모든 숫자의 합을 구하고, 그 합의 최댓값을 구하는 문제

◾ 테트로미노는 정사각형 블록이 4개입니다.

✅ 입출력

변수 설명

n m : n x m (세로/가로)

종이에 쓰여 있는 수 : n 개의 줄

return 테트로미노가 놓인 칸의 모든 합의 최댓

✔️ 예제 1

✔️ 예제 2

✔️ 예제 3

📑 문제 풀이

with 파이썬 (Python)
1시간 20분

import sys

#sys.stdin = open('input.txt', 'rt')
input = sys.stdin.readline
n, m = map(int, input().split())  # 세로 x 가로
mp = [list(map(int, input().split())) for _ in range(n)]  # 종이맵


# 테트로미노 종류에 따라
# 일자형
def shape1():
    global max_
    # 가로
    for i in range(n):  # 0 1 2 3 4
        for j in range(m + 1 - 4):  # 0 1
            sum_ = mp[i][j] + mp[i][j + 1] + mp[i][j + 2] + mp[i][j + 3]
            max_ = max(max_, sum_)
            # print(mp[i][j], mp[i][j + 1], mp[i][j + 2], mp[i][j + 3])
    # 세로
    for i in range(n + 1 - 4):  # 0 1 2 3 4
        for j in range(m):  # 0 1
            sum_ = mp[i][j] + mp[i + 1][j] + mp[i + 2][j] + mp[i + 3][j]
            max_ = max(max_, sum_)
            # print(mp[i][j], mp[i + 1][j], mp[i + 2][j], mp[i + 3][j])


# 정사각형
def shape2():
    global max_
    for i in range(n + 1 - 2):  # 0 1 2 3
        for j in range(m + 1 - 2):  # 0 1 2 3
            sum_ = sum(mp[i][j:j + 2] + mp[i + 1][j:j + 2])
            max_ = max(max_, sum_)
            # print(mp[i][j:j + 2] + mp[i + 1][j:j + 2])


# L자형
def shape3():
    global max_
    # L
    for i in range(n + 1 - 3):  # 0 1 2
        for j in range(m + 1 - 2):  # 0 1 2 3
            sum_ = mp[i][j] + mp[i + 1][j] + mp[i + 2][j] + mp[i + 2][j + 1]
            max_ = max(max_, sum_)
            # print(mp[i][j], mp[i + 1][j], mp[i + 2][j], mp[i + 2][j + 1])
    # L 대칭
    for i in range(n + 1 - 3):  # 0 1 2
        for j in range(m + 1 - 2):  # 0 1 2 3
            sum_ = mp[i][j + 1] + mp[i + 1][j + 1] + mp[i + 2][j + 1] + mp[i + 2][j]
            max_ = max(max_, sum_)
            # print(mp[i][j + 1], mp[i + 1][j + 1], mp[i + 2][j + 1], mp[i + 2][j])
    # r (L 상하반전)
    for i in range(n + 1 - 3):  # 0 1 2
        for j in range(m + 1 - 2):  # 0 1 2 3
            sum_ = mp[i][j] + mp[i][j + 1] + mp[i + 1][j + 1] + mp[i + 2][j + 1]
            max_ = max(max_, sum_)
            # print(mp[i][j], mp[i + 1][j], mp[i + 2][j], mp[i][j + 1])
    # r 대칭
    for i in range(n + 1 - 3):  # 0 1 2
        for j in range(m + 1 - 2):  # 0 1 2 3
            sum_ = mp[i][j] + mp[i + 1][j] + mp[i + 2][j] + mp[i][j + 1]
            max_ = max(max_, sum_)
            # print(mp[i][j], mp[i][j + 1], mp[i + 1][j + 1], mp[i + 2][j + 1])
    # ㄴ
    for i in range(n + 1 - 2):  # 0 1 2 3
        for j in range(m + 1 - 3):  # 0 1 2
            sum_ = mp[i][j] + mp[i + 1][j] + mp[i + 1][j + 1] + mp[i + 1][j + 2]
            max_ = max(max_, sum_)
            # print(mp[i][j], mp[i + 1][j], mp[i + 1][j + 1], mp[i + 1][j + 2])
    # ㄴ 대칭
    for i in range(n + 1 - 2):  # 0 1 2 3
        for j in range(m + 1 - 3):  # 0 1 2
            sum_ = mp[i][j + 2] + mp[i + 1][j] + mp[i + 1][j + 1] + mp[i + 1][j + 2]
            max_ = max(max_, sum_)
            # print(mp[i][j + 2], mp[i + 1][j], mp[i + 1][j + 1], mp[i + 1][j + 2])
    # ㄴ 상하반전좌우대칭
    for i in range(n + 1 - 2):  # 0 1 2 3
        for j in range(m + 1 - 3):  # 0 1 2
            sum_ = mp[i][j] + mp[i][j + 1] + mp[i][j + 2] + mp[i + 1][j]
            max_ = max(max_, sum_)
            # print(mp[i][j], mp[i][j + 1], mp[i][j + 2], mp[i + 1][j])
    # ㄱ (ㄴ 상하반전)
    for i in range(n + 1 - 2):  # 0 1 2 3
        for j in range(m + 1 - 3):  # 0 1 2
            sum_ = mp[i][j] + mp[i][j + 1] + mp[i][j + 2] + mp[i + 1][j + 2]
            max_ = max(max_, sum_)
            # print(mp[i][j], mp[i][j + 1], mp[i][j + 2], mp[i + 1][j + 2])


# 의자형
def shape4():
    global max_
    # 세로
    for i in range(n + 1 - 3):  # 0 1 2
        for j in range(m + 1 - 2):  # 0 1 2 3
            sum_ = mp[i][j] + mp[i + 1][j] + mp[i + 1][j + 1] + mp[i + 2][j + 1]
            max_ = max(max_, sum_)
            # print(mp[i][j], mp[i + 1][j], mp[i + 1][j + 1], mp[i + 2][j + 1])
    # 세로 대칭
    for i in range(n + 1 - 3):  # 0 1 2
        for j in range(m + 1 - 2):  # 0 1 2 3
            sum_ = mp[i][j + 1] + mp[i + 1][j] + mp[i + 1][j + 1] + mp[i + 2][j]
            max_ = max(max_, sum_)
            # print(mp[i][j + 1], mp[i + 1][j], mp[i + 1][j + 1], mp[i + 2][j])
    # 가로
    for i in range(n + 1 - 2):  # 0 1 2 3
        for j in range(m + 1 - 3):  # 0 1 2
            sum_ = mp[i + 1][j] + mp[i + 1][j + 1] + mp[i][j + 1] + mp[i][j + 2]
            max_ = max(max_, sum_)
            # print(mp[i + 1][j], mp[i + 1][j + 1], mp[i][j + 1], mp[i][j + 2])
    # 가로 대칭
    for i in range(n + 1 - 2):  # 0 1 2 3
        for j in range(m + 1 - 3):  # 0 1 2
            sum_ = mp[i][j] + mp[i][j + 1] + mp[i + 1][j + 1] + mp[i + 1][j + 2]
            max_ = max(max_, sum_)
            # print(mp[i][j], mp[i][j + 1], mp[i + 1][j + 1], mp[i + 1][j + 2])


# ㅜ형
def shape5():
    global max_
    # ㅜ
    for i in range(n + 1 - 2):  # 0 1 2 3
        for j in range(m + 1 - 3):  # 0 1 2
            sum_ = sum(mp[i][j:j + 3]) + mp[i + 1][j + 1]
            max_ = max(max_, sum_)
            # print(mp[i][j:j + 3], mp[i + 1][j + 1])
    # ㅗ
    for i in range(1, n):  # 1 2 3 4
        for j in range(m + 1 - 3):  # 0 1 2
            sum_ = sum(mp[i][j:j + 3]) + mp[i - 1][j + 1]
            max_ = max(max_, sum_)
            # print(mp[i][j:j + 3], mp[i - 1][j + 1])
    # ㅏ
    for i in range(n + 1 - 3):  # 0 1 2
        for j in range(m + 1 - 2):  # 0 1 2 3
            sum_ = mp[i][j] + mp[i + 1][j] + mp[i + 2][j] + mp[i + 1][j + 1]
            max_ = max(max_, sum_)
            # print(mp[i][j], mp[i + 1][j], mp[i + 2][j], mp[i + 1][j + 1])
    # ㅓ
    for i in range(n + 1 - 3):  # 0 1 2
        for j in range(1, m):  # 0 1 2 3
            sum_ = mp[i][j] + mp[i + 1][j] + mp[i + 2][j] + mp[i + 1][j - 1]
            max_ = max(max_, sum_)
            # print(mp[i][j], mp[i + 1][j], mp[i + 2][j], mp[i + 1][j - 1])


if __name__ == '__main__':
    max_ = 0
    shape1()
    shape2()
    shape3()
    shape4()
    shape5()
    print(max_)

💬 Point

➡️ 나올 수 있는 모든 도형을 생각해야한다.
➡️ n, m 범위에 주의한다.

input = sys.stdin.readline
n, m = map(int, input().split())  # 세로 x 가로
mp = [list(map(int, input().split())) for _ in range(n)]  # 종이맵

◾ 입력을 우선 받습니다.

# 테트로미노 종류에 따라
# 일자형
def shape1():
    global max_
    # 가로
    for i in range(n):  # 0 1 2 3 4
        for j in range(m + 1 - 4):  # 0 1
            sum_ = mp[i][j] + mp[i][j + 1] + mp[i][j + 2] + mp[i][j + 3]
            max_ = max(max_, sum_)
            # print(mp[i][j], mp[i][j + 1], mp[i][j + 2], mp[i][j + 3])
    # 세로
    for i in range(n + 1 - 4):  # 0 1 2 3 4
        for j in range(m):  # 0 1
            sum_ = mp[i][j] + mp[i + 1][j] + mp[i + 2][j] + mp[i + 3][j]
            max_ = max(max_, sum_)
            # print(mp[i][j], mp[i + 1][j], mp[i + 2][j], mp[i + 3][j])

◾ 일자형 테트로미노를 확인해보겠습니다. 두 개의 도형을 살펴봐야합니다.

가로형은 n 은 세로를 다 도므로 0 ~ n 까지 돕니다. 가로는 길이가 4가 되므로 바깥 범위를 넘지않도록 합니다.

세로형은 반대와 같습니다. 세로의 길이가 4가 되므로 바깥 범위를 넘지 않도록 합니다.

# 정사각형
def shape2():
    global max_
    for i in range(n + 1 - 2):  # 0 1 2 3
        for j in range(m + 1 - 2):  # 0 1 2 3
            sum_ = sum(mp[i][j:j + 2] + mp[i + 1][j:j + 2])
            max_ = max(max_, sum_)
            # print(mp[i][j:j + 2] + mp[i + 1][j:j + 2])

◾ 슬라이싱을 사용했습니다. 이도 바깥 범위를 넘지않도록 해야합니다. 정사각형이니 2씩 잡아줘야합니다.

# L자형
def shape3():
    global max_
    # L
    for i in range(n + 1 - 3):  # 0 1 2
        for j in range(m + 1 - 2):  # 0 1 2 3
            sum_ = mp[i][j] + mp[i + 1][j] + mp[i + 2][j] + mp[i + 2][j + 1]
            max_ = max(max_, sum_)
            # print(mp[i][j], mp[i + 1][j], mp[i + 2][j], mp[i + 2][j + 1])
    # L 대칭
    for i in range(n + 1 - 3):  # 0 1 2
        for j in range(m + 1 - 2):  # 0 1 2 3
            sum_ = mp[i][j + 1] + mp[i + 1][j + 1] + mp[i + 2][j + 1] + mp[i + 2][j]
            max_ = max(max_, sum_)
            # print(mp[i][j + 1], mp[i + 1][j + 1], mp[i + 2][j + 1], mp[i + 2][j])
    # r (L 상하반전)
    for i in range(n + 1 - 3):  # 0 1 2
        for j in range(m + 1 - 2):  # 0 1 2 3
            sum_ = mp[i][j] + mp[i][j + 1] + mp[i + 1][j + 1] + mp[i + 2][j + 1]
            max_ = max(max_, sum_)
            # print(mp[i][j], mp[i + 1][j], mp[i + 2][j], mp[i][j + 1])
    # r 대칭
    for i in range(n + 1 - 3):  # 0 1 2
        for j in range(m + 1 - 2):  # 0 1 2 3
            sum_ = mp[i][j] + mp[i + 1][j] + mp[i + 2][j] + mp[i][j + 1]
            max_ = max(max_, sum_)
            # print(mp[i][j], mp[i][j + 1], mp[i + 1][j + 1], mp[i + 2][j + 1])
    # ㄴ
    for i in range(n + 1 - 2):  # 0 1 2 3
        for j in range(m + 1 - 3):  # 0 1 2
            sum_ = mp[i][j] + mp[i + 1][j] + mp[i + 1][j + 1] + mp[i + 1][j + 2]
            max_ = max(max_, sum_)
            # print(mp[i][j], mp[i + 1][j], mp[i + 1][j + 1], mp[i + 1][j + 2])
    # ㄴ 대칭
    for i in range(n + 1 - 2):  # 0 1 2 3
        for j in range(m + 1 - 3):  # 0 1 2
            sum_ = mp[i][j + 2] + mp[i + 1][j] + mp[i + 1][j + 1] + mp[i + 1][j + 2]
            max_ = max(max_, sum_)
            # print(mp[i][j + 2], mp[i + 1][j], mp[i + 1][j + 1], mp[i + 1][j + 2])
    # ㄴ 상하반전좌우대칭
    for i in range(n + 1 - 2):  # 0 1 2 3
        for j in range(m + 1 - 3):  # 0 1 2
            sum_ = mp[i][j] + mp[i][j + 1] + mp[i][j + 2] + mp[i + 1][j]
            max_ = max(max_, sum_)
            # print(mp[i][j], mp[i][j + 1], mp[i][j + 2], mp[i + 1][j])
    # ㄱ (ㄴ 상하반전)
    for i in range(n + 1 - 2):  # 0 1 2 3
        for j in range(m + 1 - 3):  # 0 1 2
            sum_ = mp[i][j] + mp[i][j + 1] + mp[i][j + 2] + mp[i + 1][j + 2]
            max_ = max(max_, sum_)
            # print(mp[i][j], mp[i][j + 1], mp[i][j + 2], mp[i + 1][j + 2])

◾ 가장 도형의 개수가 많고 골치 아픈 경우입니다. 하지만 차근차근 하나씩 해보면 됩니다.

헷갈리므로 디버깅을 해가면서 합시다.

# 의자형
def shape4():
    global max_
    # 세로
    for i in range(n + 1 - 3):  # 0 1 2
        for j in range(m + 1 - 2):  # 0 1 2 3
            sum_ = mp[i][j] + mp[i + 1][j] + mp[i + 1][j + 1] + mp[i + 2][j + 1]
            max_ = max(max_, sum_)
            # print(mp[i][j], mp[i + 1][j], mp[i + 1][j + 1], mp[i + 2][j + 1])
    # 세로 대칭
    for i in range(n + 1 - 3):  # 0 1 2
        for j in range(m + 1 - 2):  # 0 1 2 3
            sum_ = mp[i][j + 1] + mp[i + 1][j] + mp[i + 1][j + 1] + mp[i + 2][j]
            max_ = max(max_, sum_)
            # print(mp[i][j + 1], mp[i + 1][j], mp[i + 1][j + 1], mp[i + 2][j])
    # 가로
    for i in range(n + 1 - 2):  # 0 1 2 3
        for j in range(m + 1 - 3):  # 0 1 2
            sum_ = mp[i + 1][j] + mp[i + 1][j + 1] + mp[i][j + 1] + mp[i][j + 2]
            max_ = max(max_, sum_)
            # print(mp[i + 1][j], mp[i + 1][j + 1], mp[i][j + 1], mp[i][j + 2])
    # 가로 대칭
    for i in range(n + 1 - 2):  # 0 1 2 3
        for j in range(m + 1 - 3):  # 0 1 2
            sum_ = mp[i][j] + mp[i][j + 1] + mp[i + 1][j + 1] + mp[i + 1][j + 2]
            max_ = max(max_, sum_)
            # print(mp[i][j], mp[i][j + 1], mp[i + 1][j + 1], mp[i + 1][j + 2])

◾ 회전을 하고 대칭을 해서 4개의 도형을 찾아 합을 구해봅니다.

# ㅜ형
def shape5():
    global max_
    # ㅜ
    for i in range(n + 1 - 2):  # 0 1 2 3
        for j in range(m + 1 - 3):  # 0 1 2
            sum_ = sum(mp[i][j:j + 3]) + mp[i + 1][j + 1]
            max_ = max(max_, sum_)
            # print(mp[i][j:j + 3], mp[i + 1][j + 1])
    # ㅗ
    for i in range(1, n):  # 1 2 3 4
        for j in range(m + 1 - 3):  # 0 1 2
            sum_ = sum(mp[i][j:j + 3]) + mp[i - 1][j + 1]
            max_ = max(max_, sum_)
            # print(mp[i][j:j + 3], mp[i - 1][j + 1])
    # ㅏ
    for i in range(n + 1 - 3):  # 0 1 2
        for j in range(m + 1 - 2):  # 0 1 2 3
            sum_ = mp[i][j] + mp[i + 1][j] + mp[i + 2][j] + mp[i + 1][j + 1]
            max_ = max(max_, sum_)
            # print(mp[i][j], mp[i + 1][j], mp[i + 2][j], mp[i + 1][j + 1])
    # ㅓ
    for i in range(n + 1 - 3):  # 0 1 2
        for j in range(1, m):  # 0 1 2 3
            sum_ = mp[i][j] + mp[i + 1][j] + mp[i + 2][j] + mp[i + 1][j - 1]
            max_ = max(max_, sum_)
            # print(mp[i][j], mp[i + 1][j], mp[i + 2][j], mp[i + 1][j - 1])

◾ 이도 4개의 도형이 있습니다. 이렇게 하나하나 도형을 따져보면서 합을 구하면 최종값을 구할 수 있습니다.

# 알고리즘 백준 테트로미노 파이썬

# 알고리즘 bj14500 python 테트로미노

728x90

저작자표시 비영리 변경금지

'✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺 > 백준 알고리즘' 카테고리의 다른 글

[BJ14502] 연구소 (0)	2022.05.04
[BJ14501] 퇴사 (0)	2022.04.30
[BJ14499] 주사위 굴리기 (0)	2022.04.29
[BJ13458] 시험 감독 (0)	2022.04.28
[BJ3190] 뱀 (0)	2022.04.28

🚩 문제 설명

✅ 입출력

📑 문제 풀이

'✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺 > 백준 알고리즘' 카테고리의 다른 글

티스토리툴바