백준 14500번 테트로미노

백준 14500번 테트로미노

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

코드

import sys

def shape_stick(r, c):
  score = 0
  # 정방향
  if c+3 < M:
    count = 0
    for i in range(4):
      count += board[r][c+i]
    score = max(score, count)
  # 회전
  if r+3 < N:
    count = 0
    for i in range(4):
      count += board[r+i][c]
    score = max(score, count)
  
  return score

def shape_squre(r, c):
  score = 0
  # 정방향
  if c+1 < M and r+1 < N:
    for i in range(2):
      for v in range(2):
        score += board[r+i][c+v]
  return score

def shape_L(r, c):
  score = 0
  # 정방향
  if r+2 < N and c+1 < M:
    count = 0
    for i in range(3):
      count += board[r+i][c]
    count += board[r+2][c+1]  
    score = max(score, count)
  # 90도 회전
  if r+1 < N and c+2 < M:
    count = 0
    for i in range(3):
      count += board[r][c+i]
    count += board[r+1][c]
    score = max(score, count)
  # 180도 회전
  if r+2 < N and c+1 < M:
    count = 0
    for i in range(3):
      count += board[r+i][c+1]
    count += board[r][c]
    score = max(score, count)
  # 270도 회전
  if 0 <= r-1 and c+2 < M:
    count = 0
    for i in range(3):
      count += board[r][c+i]
    count += board[r-1][c+2]
    score = max(score, count)
  
  # 대칭
  if r+2 < N and c-1 >= 0:
    count = 0
    for i in range(3):
      count += board[r+i][c]
    count += board[r+2][c-1]  
    score = max(score, count)
  
  # 대칭, 90도 회전
  if r+1 < N and c+2 < M:
    count = 0
    for i in range(3):
      count += board[r+1][c+i]
    count += board[r][c]  
    score = max(score, count)
  
  # 대칭, 180도 회전
  if r+2 < N and c+1 < M:
    count = 0
    for i in range(3):
      count += board[r+i][c]
    count += board[r][c+1]  
    score = max(score, count)
  
  # 대칭, 270도 회전
  if r+1 < N and c+2 < M:
    count = 0
    for i in range(3):
      count += board[r][c+i]
    count += board[r+1][c+2]  
    score = max(score, count)

  return score

def shape_lightning(r, c):
  score = 0
  # 정방향
  if r+2 < N and c+1 < M:
    count = 0
    for i in range(2):
      count += board[r+1][c+i]
    count += board[r][c]  
    count += board[r+2][c+1]  
    score = max(score, count)
  # 90도 회전
  if 0 <= r-1 and c+2 < M:
    count = 0
    for i in range(2):
      count += board[r-1+i][c+1]
    count += board[r][c]  
    count += board[r-1][c+2]  
    score = max(score, count)
  # 대칭
  if 0 <= r-2 and c+1 < M:
    count = 0
    for i in range(2):
      count += board[r-1][c+i]
    count += board[r][c]  
    count += board[r-2][c+1]  
    score = max(score, count)
  # 대칭 90도 회전
  if r+1 < N and c+2 < M:
    count = 0
    for i in range(2):
      count += board[r+i][c+1]
    count += board[r][c]  
    count += board[r+1][c+2]  
    score = max(score, count)

  return score

def shape_last(r, c):
  score = 0
  # 정방향
  if r+1 < N and c+2 < M:
    count = 0
    for i in range(3):
      count += board[r][c+i]
    count += board[r+1][c+1]    
    score = max(score, count)
  # 90도 회전
  if r+2 < N and 0 <= c-1:
    count = 0
    for i in range(3):
      count += board[r+i][c]
    count += board[r+1][c-1]    
    score = max(score, count)
  # 180도 회전
  if 0 <= r-1 and c+2 < M:
    count = 0
    for i in range(3):
      count += board[r][c+i]
    count += board[r-1][c+1]    
    score = max(score, count)
  # 270도 회전
  if r+2 < N and c+1 < M:
    count = 0
    for i in range(3):
      count += board[r+i][c]
    count += board[r+1][c+1]    
    score = max(score, count)
  
  return score


N, M = map(int, sys.stdin.readline().split())
board = []

for i in range(N):
  board.append(list(map(int, sys.stdin.readline().split())))
  
result = 0
for i in range(N):
  for j in range(M):
    result = max(result, shape_stick(i, j))
    result = max(result, shape_squre(i, j))
    result = max(result, shape_L(i, j))
    result = max(result, shape_lightning(i, j))
    result = max(result, shape_last(i, j))
  
print(result)

문제풀이

이 문제는 각 모양의 회전과 대칭을 모두 고려하여 최종합의 최댓값을 측정해야합니다.

그렇기에 각 모양의 대한 회전 및 대칭을 모두 구현을 해야합니다. 저 같은 경우에는 각 경우를 모양으로 나누고 모두 조건문과 반목문을 통해서 구현했습니다.

좀 더 코드를 깔끔하게 구현하기 위해서는 각 모양들을 좌표로만 표현하여 구현할 수도 있을 겁니다. 하지만 좀더 가시성이나 나중에 수정의 경우가 생겼을 때 용이하도록 직접 다 코드를 구현했습니다.

알고리즘 문제풀이와 숏코딩을 위한 방법으로는 옳바르지 않을 수 있으나 코드의 가독성이나 관리에서는 조금 더(?) 나은 방법이 아닌가 싶습니다.

문제는 어렵지 않았으나 각 모양의 구현을 위해서 생각 및 노트에 적으면서 풀이 하니 시간이 오래걸렸던 것 같습니다...