문제
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.
https://www.acmicpc.net/problem/14500
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.
- 정사각형은 서로 겹치면 안 된다.
- 도형은 모두 연결되어 있어야 한다.
- 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.
아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.
테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.
테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.
입력
- 첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)
- 둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다.
- i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다.
- 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.
출력
- 첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.
풀이
완전탐색으로도 가능해보이지만 구현이 더 빨라보이는 문제다.
DP로 혹시 빠르게 풀 수 있지 않을까싶어 BFS, DFS, DP 등 다양하게 생각해봤는데 아직까진 명확한 해답을 찾지 못했다. 오히려 경우의 수가 19개 밖에 되지 않아 구현으로 빠르게 푸는게 더 효율적으로 보이기까지 하다. (아직 멀었다~~)
경우의 수를 조금 보기 쉽게 그림으로 나타내봤다. (더 복잡해보이는건 기분탓인가?)
설명
- 모든 경우의 수를 좌표 형식으로 배열에 저장해둔다.
- 모든 점에서 19가지 경우의 수를 다 돌아보며 최대값을 찾는다.
- 푼 사람마다 좌표를 저장하는 방식이 조금씩 다른데, 나는 방문하는 점을
0,0으로 정해 기준으로 삼고 다른 점들을 배치했다.
답
from sys import stdin
from collections import deque
input = stdin.readline
def tetromino(a, n, m):
ret = 0
di = [
# 일자
[[0, 0], [0, 1], [0, 2], [0, 3]], [[0, 0], [1, 0], [2, 0], [3, 0]],
# 네모
[[0, 0], [0, 1], [1, 0], [1, 1]],
# 기억
[[0, 0], [0, 1], [0, 2], [1, 0]], [[0, 0], [0, 1], [0, 2], [-1, 2]],
[[0, 0], [1, 0], [1, 1], [1, 2]], [[0, 0], [0, 1], [0, 2], [1, 2]],
[[0, 0], [1, 0], [2, 0], [2, 1]], [[0, 0], [1, 0], [2, 0], [2, -1]],
[[0, 0], [0, 1], [1, 0], [2, 0]], [[0, 0], [0, 1], [1, 1], [2, 1]],
# 볼록할 철
[[0, 0], [0, 1], [0, 2], [1, 1]], [[0, 0], [0, 1], [0, 2], [-1, 1]],
[[0, 0], [1, 0], [1, 1], [2, 0]], [[0, 0], [1, 0], [2, 0], [1, -1]],
# 번개
[[0, 0], [1, 0], [1, -1], [2, -1]], [[0, 0], [1, 0], [1, 1], [2, 1]],
[[0, 0], [0, 1], [-1, 1], [-1, 2]], [[0, 0], [0, 1], [1, 1], [1, 2]]
]
for x in range(n):
for y in range(m):
for d in di:
four = 0
for i in range(4):
xi = x + d[i][0]
yi = y + d[i][1]
if 0 <= xi < n and 0 <= yi < m:
four += a[xi][yi]
ret = max(ret, four)
return ret
if __name__ == "__main__":
N, M = map(int, input().split())
array = [list(map(int, input().split())) for _ in range(N)]
res = tetromino(array, N, M)
print(res)
Uploaded by Notion2Tistory v1.1.0