[백준] 14500 테트로미노 (파이썬)

골드 Ⅳ

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

14500번: 테트로미노

 

📄 문제

• 크기가 N×M인 종이 위에 테트로미노 ★하나를 놓으려고 한다.
• 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.
• 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 5가지가 모양이 있다.
• 테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

 

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

 

---

💡 아이디어

1. ㅜ 모양을 제외한 4가지 모양은 DFS 깊이 탐색으로 구현이 가능하다.
   • 상하좌우로 움직이면서 깊이 4까지 탐색한다.
   • ㅜ 모양을 제외한 4가지 모양을 회전, 대칭한 모양이 다 만들어진다.
2. ㅜ 모양은 DFS로 탐색할 때 깊이 2 위치에서 2번 탐색하던지, 따로 구현하던지 하면 된다.
3. 깊이 4 까지 DFS 탐색하면서 종이 위에 정수 값을 더해 최댓값을 구한다.

 

📝 문제 풀이 (Code)

import sys
input = sys.stdin.readline

def dfs(i, j, ssum, idx):
    global ans

    if idx == 4:
        ans = max(ans, ssum)
        return

    for k in range(4):
        ni = i + di[k]
        nj = j + dj[k]

        if 0 <= ni < n and 0 <= nj < m and not visited[ni][nj]:
            visited[ni][nj] = 1
            dfs(ni, nj, ssum + arr[ni][nj], idx + 1)
            visited[ni][nj] = 0

            # ㅜ 모양, 깊이 2에서 한번 더 탐색
            if idx == 2:
                visited[ni][nj] = 1
                dfs(i, j, ssum + arr[ni][nj], idx + 1)
                visited[ni][nj] = 0


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

arr = [list(map(int, input().split())) for _ in range(n)]

# N×M인 종이 위에 테트로미노 하나를 놓으려고 한다.
# dfs 깊이 4 까지 탐색

di = [0, 1, 0, -1]
dj = [1, 0, -1, 0]

visited = [[0]*m for _ in range(n)]
ans = 0

for i in range(n):
    for j in range(m):
        visited[i][j] = 1
        dfs(i, j, arr[i][j], 1)
        visited[i][j] = 0

print(ans)