*문제 출처는 백준에 있습니다.
문제 제목: 테트로미노 / 14500번 (골드 4단계)
문제 사이트: https://www.acmicpc.net/problem/14500
문제 설명

나의 풀이
# 정답
answer = 0
def solution(n, m, block):
global answer
answer = 0 # 수정됨: 여러 테스트 케이스가 있을 경우 초기화 필요
# 이동 방향 (상, 하, 좌, 우)
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
visited = [[False] * m for _ in range(n)]
def dfs(iy, ix, count, total):
global answer
if count == 4:
answer = max(answer, total)
return
for ny, nx in move:
y = iy + ny
x = ix + nx
if 0 <= y < n and 0 <= x < m and not visited[y][x]:
visited[y][x] = True
dfs(y, x, count + 1, total + block[y][x]) # 수정됨: block[i][j] → block[y][x]
visited[y][x] = False
# DFS 탐색: ㅗ 제외한 테트로미노 모양
for i in range(n):
for j in range(m):
visited[i][j] = True
dfs(i, j, 1, block[i][j])
visited[i][j] = False
# ㅗ, ㅏ, ㅓ, ㅜ 모양 (중간 분기형)
shapes = [
[(0, 0), (0, 1), (0, 2), (1, 1)], # ㅗ
[(0, 0), (1, 0), (2, 0), (1, 1)], # ㅏ
[(0, 0), (1, -1), (1, 0), (1, 1)], # ㅜ
[(0, 0), (1, -1), (1, 0), (2, 0)] # ㅓ
]
# 하드코딩 탐색: ㅗ 계열 모양
for i in range(n):
for j in range(m):
for shape in shapes:
total = 0
valid = True
for dy, dx in shape:
y = i + dy
x = j + dx
if 0 <= y < n and 0 <= x < m:
total += block[y][x]
else:
valid = False
break
if valid:
answer = max(answer, total)
def main():
n, m = map(int, input().split())
block = [list(map(int, input().split())) for _ in range(n)]
solution(n, m, block)
print(answer)
if __name__ == "__main__":
main()

※ 알아야 할 것
처음에는 ㅗ 계열 모양을 생각 안했어서 바로 되는 줄 알 았는데 따로 계산을 해야합니다! 그리고 문제 조건을 보면
"테트로미노 하나를 종이에 적절히 놓아서, 그 위에 적힌 숫자들의 합의 최댓값을 구하라"고 나와 있습니다.
혹시나 여러 테트로미노를 올려야 한다고 착각하실 수 있어서 올렸습니다. 테트로미노 여러 개를 조합해서 전체 맵을 덮는 문제를 생각한 거라면 그런 문제는 테트로미노 타일링 문제라고 합니다!
'Coding Test > 백준-Python' 카테고리의 다른 글
| 백준 / 로또 / 6603번 / Python (0) | 2025.05.12 |
|---|---|
| 백준 / 카드 구매하기 / 11052번 / Python (0) | 2025.05.11 |
| 백준 / 다리 만들기 2 / 17472번 / Python (0) | 2025.05.07 |
| 백준 / 빵집 / 3109번 / Python (0) | 2025.05.06 |
| 백준 / 경로 찾기 / 11403번 / Python (0) | 2025.05.05 |