[14500] 테트로미노 (골드 5)

isanghaessi·2022년 2월 5일
0

백준

목록 보기
6/10

14500번: 테트로미노

보드가 주어졌을 때, 4칸짜리 테트로미노(대각선 없이 연결된 모양)중 합이 가장 큰 경우를 찾는 문제다.

고려했던 사항은 다음과 같다.

  • 테트로미노는 4칸짜리 라면 어떤 모양이든 된다.
    • 문제에서는 5개 조각을 회전, 대칭할 수 있다고 주어졌는데 모든 경우가 포함된다.

풀이 과정은 다음과 같다.

  • 보드를 2차원 배열로 가지고 모든 칸을 순회한다.
  • bfs를 통해서 붙일 수 있는 칸중에서 가장 높은 칸을 붙인다.
  • 칸이 4개가 되면 answer를 answer와 현재 합중 큰 값으로 업데이트 한다.

이 문제는 정말 애를 먹었다... 처음에는 dfs로 모든 경우를 찾으면서 이미 돌아본 블럭 모음(테트로미노)는 뛰어넘는 식으로 하려 했지만 dfs의 경우 ㅗ모양을 빠뜨려야 했다. 그래서, bfs로 접근하고 처음에는 브루트 포스로 모든 경우를 계산했지만 메모리/시간 초과가 나와서 최대 값을 가지는 블록만 붙이는 식으로 변경했다. 아직은 경험이 부족해서 시간도 오래걸리고, 이상한 방향으로 풀이를 잡는 경우가 많은것 같다. 연습하자... 백준에서 풀이를 보니 대부분 모든 경우의 수(블록 offset)을 만든 후에 순회하는 식으로 짰다. 테스트 당시에는 오히려 풀이 시간을 단축할 수 있겠다는 생각을 했다.

import sys

def bfs():
  global answer

  if len(block) == 4:
    blockSum = sum(map(lambda a: board[a[0]][a[1]], block))
    answer = max(answer, blockSum)

    return False
  blockSum = 0
  nearBlocks = []
  for bi, bj in block:
    if bi - 1 >= 0 and (bi - 1, bj) not in block:
      nearBlocks.append((board[bi - 1][bj], bi - 1, bj))
    if bi + 1 < n and (bi + 1, bj) not in block:
      nearBlocks.append((board[bi + 1][bj], bi + 1, bj))
    if bj - 1 >= 0 and (bi, bj - 1) not in block:
      nearBlocks.append((board[bi][bj - 1], bi, bj - 1))
    if bj + 1 < m and (bi, bj + 1) not in block:
      nearBlocks.append((board[bi][bj + 1], bi, bj + 1))
  block.append(tuple(max(nearBlocks, key = lambda a: a[0])[1:]))

  return True

n, m = map(int, sys.stdin.readline().strip().split(' '))
board = [[] for _ in range(n)]
for i in range(n):
  line = map(int, sys.stdin.readline().strip().split(' '))
  for l in line:
    board[i].append(l)
answer = 0
for i in range(n):
  for j in range(m):
    block = [(i, j)]
    while(bfs()):
      pass
print(answer)
profile
seungyong HONG

0개의 댓글