[백준/Python] 14500번(구현)_테트로미노

📌문제 유형

구현, 브루트포스

 

📌문제

14500번: 테트로미노

 

 

📌나의 문제풀이

- 모든 경우의 수 다 동원해서 풀이

• 각각의 블럭 모양 만들기 (단, S와 L은 좌우반전 고려해서 케이스 2개)
• 종이의 판을 90도씩 3번 돌리기 -> 블럭 고정, 종이판을 돌리기

 * 주의 : S와 L은 좌우반전하면 y <= 0인 경우로 수정하기 (수정 안하면 85%)

# ㅡ 블럭
def long_block(x,y):
    total = 0
    if x < 0 or x >= len(maps) or y < 0 or len(maps[x]) <= y+3:
        return total

    for i in range(y,y+4):
        total += maps[x][i]
    return total

# 정사각형
def square_block(x,y):
    total = 0
    if 0 > y or len(maps[x]) <= y+1 or x < 0 or len(maps) <= x+1:
        return total

    total += maps[x][y]
    total += maps[x][y+1]
    total += maps[x+1][y]
    total += maps[x+1][y+1]
    return total

# L 블럭
def L_block(x,y):
    total = 0
    if y < 0 or len(maps[x])-1 < y+1 or x < 0 or len(maps)-1 < x+2:
        return total

    for i in range(x,x+3):
        total += maps[i][y]
    total += maps[x+2][y+1]
    return total

def L_block_2(x,y):
    total = 0
    if y <= 0 or len(maps[x])-1 < y or x < 0 or len(maps)-1 < x+2:
        return total

    for i in range(x,x+3):
        total += maps[i][y]
    total += maps[x+2][y-1]
    return total

# S 블럭
def S_block(x,y):
    total = 0
    if y < 0 or len(maps[x]) < y+2 or x < 0 or len(maps) < x+3:
        return total

    for i in range(x,x+2):
        total += maps[i][y]
    for j in range(x+1, x+3):
        total += maps[j][y+1]
    return total

def S_block_2(x,y):
    total = 0
    if y <= 0 or len(maps[x]) < y+1 or x < 0 or len(maps) < x+3:
        return total

    for i in range(x,x+2):
        total += maps[i][y]
    for j in range(x+1, x+3):
        total += maps[j][y-1]
    return total

# T 블럭
def T_block(x,y):
    total = 0
    if y < 0 or len(maps[x]) < y+3 or x < 0 or len(maps) < x+2:
        return total

    for i in range(y,y+3):
        total += maps[x][i]
    total += maps[x+1][y+1]
    return total

# 90도 회전
def rotate(arr):
    list_tuples = zip(*arr[::-1])
    return [list(l) for l in list_tuples]

n,m = map(int,input().split())

maps = []
for _ in range(n):
    rows = list(map(int,input().split()))
    maps.append(rows)

# 각 블럭별로 코드 짜고, maps를 90 도씩 옮겨서 계산하기
# return 값이 0 나오면 break로 멈추기 -> x를 다음 줄로 넘기기
ans = 0
for _ in range(4):
    for x in range(len(maps)):
        for y in range(len(maps[0])):
            a = long_block(x,y)
            b = square_block(x,y)
            c = L_block(x,y)
            d = S_block(x,y)
            e = T_block(x,y)
            f = L_block_2(x,y)
            g = S_block_2(x,y)

            result = max(a,b,c,d,e,f,g)
            if ans < result:
                ans = result
    maps = rotate(maps)
print(ans)

 

 

📌다른사람의 문제풀이

- DFS 이용 (단, ㅜ모양은 직접 만들기)

import sys
input = sys.stdin.readline

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

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

# 최대값 변수
maxValue = 0

# ㅗ, ㅜ, ㅓ, ㅏ 제외한 모양들 최대값 계산
def dfs(i, j, dsum, cnt):
    global maxValue
    # 모양 완성되었을 때 최대값 계산
    if cnt == 4:
        maxValue = max(maxValue, dsum)
        return

    # 상, 하, 좌, 우로 이동
    for n in range(4):
        ni = i+move[n][0]
        nj = j+move[n][1]
        if 0 <= ni < N and 0 <= nj < M and not visited[ni][nj]:
            # 방문 표시 및 제거
            visited[ni][nj] = True
            dfs(ni, nj, dsum + board[ni][nj], cnt+1)
            visited[ni][nj] = False


# ㅗ, ㅜ, ㅓ, ㅏ 모양의 최대값 계산
def exce(i, j):
    global maxValue
    for n in range(4):
        # 초기값은 시작지점의 값으로 지정
        tmp = board[i][j]
        for k in range(3):
            # move 배열의 요소를 3개씩 사용할 수 있도록 인덱스 계산
            # 012, 123, 230, 301
            t = (n+k)%4
            ni = i+move[t][0]
            nj = j+move[t][1]

            if not (0 <= ni < N and 0 <= nj < M):
                tmp = 0
                break
            tmp += board[ni][nj]
        # 최대값 계산
        maxValue = max(maxValue, tmp)


for i in range(N):
    for j in range(M):
        # 시작점 visited 표시
        visited[i][j] = True
        dfs(i, j, board[i][j], 1)
        visited[i][j] = False

        exce(i, j)

print(maxValue)

 

📌리뷰

- 테트로미노 모든 경우의 수 가능한지 확인

글 읽기 - << 테케 공유 >>

- 올 구현인 경우 범위 체크가 가장 중요