14500. 테트로미노 -브루트 포스, 구현, 시뮬레이션. [파이썬]

14500. 테트로미노

사용한 알고리즘/자료구조
1. 델타를 이용한 2차원 배열 탐색.
2. 브루트 포스

접근방식
테트로미노들의 상태를 모두 구현한다.
모든 경우의 수를 완전 탐색한다.

문제 특이사항
구현해야 할 양이 많은 문제다. 계획을 잘 짜고 구현하지 않으면 디버깅이 난해할 수 있다.

개선 가능한 점
1) 문제의 조건을 잘 읽고 가지를 칠 수 있다.

2) 부분합을 미리 구해둔 뒤 반복되는 연산을 생략할 수 있다. 

느낀점
상당히 배운 점이 많은 문제입니다. 처음 풀 때에는 브루트포스로 풀었으나, 갈수록 시공간 복잡도를 절약할 수 있는 다양한 방법들이 떠올랐습니다. 곧 다른 풀이들을 업로드 하겠습니다. 

문제를 풀었을 당시 백준 티어

2021-09-27, 실버 2

 

 

from sys import stdin

TETROMINOS = (
    ((0, 1), (0, 2), (0, 3)),   # 1) 가로 테트리스
    ((1, 0), (2, 0), (3, 0)),   # 2) 세로 테트리스
    ((0, 1), (1, 0), (1, 1)),   # 3) 네모
    ((1, 0), (2, 0), (2, 1)),   # 4)ㄴ 원본
    ((1, 0), (2, 0), (2, -1)),  # 5) ㄴ 좌우반전
    ((0, -1), (1, 0), (2, 0)),  # 6) ㄱ 원본
    ((0, 1), (1, 0), (2, 0)),   # 7) ㄱ 좌우반전
    ((1, 0), (1, 1), (1, 2)),   # 8) 눕힌 ㄴ
    ((0, 1), (0, 2), (-1, 2)),  # 9) 눕힌 ㄴ 반전
    ((0, 1), (0, 2), (1, 2)),   # 10) 눕힌 ㄱ
    ((0, 1), (0, 2), (1, 0)),   # 11) 눕힌 ㄱ 반전
    ((1, 0), (0, 1), (-1, 1)),  # 12) 해리포터 기본
    ((1, 0), (1, 1), (2, 1)),   # 13) 해리포터 좌우반전
    ((0, 1), (-1, 1), (-1, 2)),  # 14) 누운 해리포터
    ((0, 1), (1, 1), (1, 2)),   # 15) 누운 상하반전
    ((0, 1), (1, 1), (0, 2)),   # 16) ㅗ
    ((0, 1), (-1, 1), (0, 2)),  # 17) ㅜ
    ((-1, 0), (-1, -1), (-2, 0)),  # 18) ㅓ
    ((-1, 0), (-1, 1), (-2, 0)),  # 19) ㅏ
)


def tetro(starting_point):

    global max_total    # 글로벌 변수 선언.

    # 1) 선언
    y, x = starting_point   # 시작지점의 y, x좌표
    start_value = tetris_map[y][x]  # 시작지점의 값.

    # 2) 연산
    for tetris in TETROMINOS:   # 모든 테트로미노 모양을 순회

        # (1) 선언
        ttl = start_value   # 초기값.
        is_valid = True # 진행 가능성 여부 스위치.

        # (2) 연산
        for spot in tetris: # 모든 지점들을 순회하며
            next_y = y + spot[0]
            next_x = x + spot[1]

            # 만약 y혹은 x 좌표가 테트리스 게임판 범위를 벗어난다면
            if next_y >= N or next_x >= M \
                    or next_y < 0 or next_x < 0:

                is_valid = False    # 유효하지 않은 요청임을 표시.
                break   # 함수 종료

            # 성공할 경우,
            ttl += tetris_map[next_y][next_x]   # 현재 값 갱신

        # (3) 결과값 갱신
        if is_valid:    # 유효하다면
            max_total = max(max_total, ttl) # 최대값 갱신.


# 1. 입력
N, M = map(int, stdin.readline().split())   # 테트리스 판의 세로, 가로 길이.
tetris_map = [list(map(int, stdin.readline().split())) for _ in range(N)]   # 테트리스 판 정보

# 2. 선언
max_total = 0   # 정답 보관을 위한 변수 선언


# 3. 연산
for i in range(N):  # 모든 지점들을
    for j in range(M):  # 확인하며
        tetro((i, j))   # 문제에서 지정한 연산 수행.

# 4. 출력
print(max_total)