[Python] 백준14500 테트로미노

03 Feb 2023 in Study on Algorithm

백준14500 테트로미노 링크

문제

예제 입력

---

코드

import sys
n, m = map(int, input().split())
arr = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ]
visit = [ [False] * m for _ in range(n) ]

ans = 0
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0] 
def DFS(y, x, cnt, total):
    global ans
    if cnt == 4:
        ans = max(ans, total)
        return
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= ny < n and 0 <= nx < m and not visit[ny][nx]:
            if cnt == 2:
                visit[ny][nx] = True
                DFS(y, x, cnt+1, total+arr[ny][nx])
                visit[ny][nx] = False
            visit[ny][nx] = True
            DFS(ny, nx, cnt+1, total+arr[ny][nx])
            visit[ny][nx] = False

for i in range(n):
    for j in range(m):
        visit[i][j] = True
        DFS(i, j, 1, arr[i][j])
        visit[i][j] = False
print(ans)

설명

파이썬을 통해서 사용자로부터 입력받아 DFS알고리즘을 사용하여 테트로미노를 구현했습니다.

---

결과