[백준 🥇4] 14500번 테트로미노 (Python/파이썬)

1️⃣ 문제

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

2️⃣ 코드

테트로미노 엄청 무식하게 푼 코드..ㅋㅋㅋㅋ
테트로미노 좌표 일일이 적어서 풀었다

n, m = map(int, input().split())
paper = []
for _ in range(n):
    paper.append(list(map(int, input().split())))

dy = [[0, 0, 0, 0], [0, 1, 2, 3], [0, 1, 2, 2], [0, 1, 2, 2], [0, 0, 1, 2],
      [0, 0, 1, 2], [0, 1, 1, 1], [0, 1, 1, 1], [0, 0, 0, 1], [0, 0, 0, 1],
      [0, 0, 1, 1], [0, 1, 1, 2], [0, 1, 1, 2], [0, 0, 1, 1], [0, 0, 1, 1],
      [0, 1, 1, 1], [0, 0, 0, 1], [0, 1, 1, 2], [0, 1, 1, 2]]
dx = [[0, 1, 2, 3], [0, 0, 0, 0], [0, 0, 0, 1], [1, 1, 0, 1], [0, 1, 0, 0],
      [0, 1, 1, 1], [0, 0, 1, 2], [2, 0, 1, 2], [0, 1, 2, 0], [0, 1, 2, 2],
      [0, 1, 0, 1], [0, 0, 1, 1], [1, 0, 1, 0], [1, 2, 0, 1], [0, 1, 1, 2],
      [1, 0, 1, 2], [0, 1, 2, 1], [0, 0, 1, 0], [1, 0, 1, 1]]

answer = 0

# 19개의 폴리노미노 하나씩 시도해보기 
for i in range(19):
    for y in range(n):
        for x in range(m):
            flag = True   # 해당 폴리노미노 놓을수있는지 여부 
            temp = 0   # 해당 폴리노미노 수들의 합 
            for k in range(len(dx[i])):
                nx = x + dx[i][k]
                ny = y + dy[i][k]

                if 0 <= nx < m and 0 <= ny < n:
                    temp += paper[ny][nx]
                else:
                    flag = False
                    break

            if flag:
                answer = max(temp, answer)

print(answer)

3️⃣ 풀이

코드 속 dy, dx 리스트 순서는 사진 속 폴리노미노 번호순!

그래도 DFS 풀이는 알고 넘어가야지!
특정 좌표로부터 dfs를 거리 3까지만 돌게되면 ㅗ모양을 제외한 모든 테트로미노를 만들 수 있다
코드는 다른 분들 코드를 참고했음

n, m = map(int, input().split())
board = []
for _ in range(n):
    board.append(list(map(int, input().split())))
maxi = max(map(max, board))   # 종이 숫자 중 최댓값 
visited = [[False] * m for _ in range(n)]
answer = 0

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

def dfs(y, x, cnt, total):   # y좌표, x좌표, 탐색한 블록 개수, 수들의 합
    global answer
    if answer >= total + maxi * (4 - cnt):   # 지금 상태에서 계속 최댓값이 나와도 answer보다 작을 경우
        return

    if cnt == 4:
        answer = max(total, answer)
        return

    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < n and 0 <= nx < m and not visited[ny][nx]:
            if cnt == 2:   # ㅗ모양을 만들어주기 위해, 두개의 블록을 탐색했을 때
                visited[ny][nx] = True
                dfs(y, x, cnt+1, total+board[ny][nx])
                visited[ny][nx] = False

            visited[ny][nx] = True
            dfs(ny, nx, cnt+1, total+board[ny][nx])
            visited[ny][nx] = False
                
            
for y in range(n):
    for x in range(m):
        visited[y][x] = True
        dfs(y, x, 1, board[y][x])
        visited[y][x] = False

print(answer)

시간 엄청 줄었다....!