[백준] 14500 : 테트로미노 - Python

코드

import sys
sys.stdin = open("input.txt", "rt")

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

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

boards = [
    [
        [1,1,1,1],
        [0,0,0,0],
        [0,0,0,0],
        [0,0,0,0]
    ],
    [
        [1,0,0,0],
        [1,0,0,0],
        [1,0,0,0],
        [1,0,0,0]
    ],
    [
        [1,1,0,0],
        [1,1,0,0],
        [0,0,0,0],
        [0,0,0,0]
    ],
    [
        [1,0,0,0],
        [1,0,0,0],
        [1,1,0,0],
        [0,0,0,0]
    ],
    [
        [1,1,1,0],
        [1,0,0,0],
        [0,0,0,0],
        [0,0,0,0]
    ],
    [
        [1,1,0,0],
        [0,1,0,0],
        [0,1,0,0],
        [0,0,0,0]
    ],
    [
        [0,0,1,0],
        [1,1,1,0],
        [0,0,0,0],
        [0,0,0,0]
    ],
    [
        [0,1,0,0],
        [0,1,0,0],
        [1,1,0,0],
        [0,0,0,0]
    ],
    [
        [1,0,0,0],
        [1,1,1,0],
        [0,0,0,0],
        [0,0,0,0]
    ],
    [
        [1,1,0,0],
        [1,0,0,0],
        [1,0,0,0],
        [0,0,0,0]
    ],
    [
        [1,1,1,0],
        [0,0,1,0],
        [0,0,0,0],
        [0,0,0,0]
    ],
    [
        [1,0,0,0],
        [1,1,0,0],
        [0,1,0,0],
        [0,0,0,0]
    ],
    [
        [0,1,1,0],
        [1,1,0,0],
        [0,0,0,0],
        [0,0,0,0]
    ],
    [
        [0,1,0,0],
        [1,1,0,0],
        [1,0,0,0],
        [0,0,0,0]
    ],
    [
        [1,1,0,0],
        [0,1,1,0],
        [0,0,0,0],
        [0,0,0,0]
    ],
    [
        [1,0,0,0],
        [1,1,0,0],
        [1,0,0,0],
        [0,0,0,0]
    ],
    [
        [1,1,1,0],
        [0,1,0,0],
        [0,0,0,0],
        [0,0,0,0]
    ],
    [
        [0,1,0,0],
        [1,1,0,0],
        [0,1,0,0],
        [0,0,0,0]
    ],
    [
        [0,1,0,0],
        [1,1,1,0],
        [0,0,0,0],
        [0,0,0,0]
    ]
]

# ! 19가지 모든 경우의 수 생각
def isInner(x,y):
    if 0<=x<n and 0<=y<m:
        return True
    return False

#!  주어진 위치에 대하여 가능한 모든 모양 탐색, 최대 합 반환
def get_max_sum(startX,startY): # ! 현재 위치 기준으로 19개 모두 확인
    maxSum = 0
    for board in boards: # ! 보드 하나씩 꺼내 -> 4x4
        nowSum = 0
        for dx in range(4):
            for dy in range(4):
                if board[dx][dy] == 1: # ! 격자 부분의 합만 구해야지
                    if isInner(startX + dx, startY + dy):
                        nowSum += g[startX + dx][startY + dy]
        maxSum = max(maxSum,nowSum)
    return maxSum

MAX = -int(1e9)
for x in range(n):
    for y in range(m): # ! 현재 위치에서 매번 계산
        get = get_max_sum(x,y)
        MAX = max(MAX, get)
print(MAX)

코멘트

해당 문제 어떻게 풀 것인가.

빡구현 -> 직접 모든 경우를 생각해보자. 그리고 직접 돌려보면서 되는지 손으로 체크해봐야해.

1. 현재 위치에서 19개의 블록 모두를 확인
2. 현재 위치에서 테트로미노 모양의 가로 세로 (4x4) 확인
3. 모양이 있는 부분만 점수 계산

격자 안에 있다면 해당 위치 점수를 구해서 합을 비교
-> 최대 점수 계산하면 된다.

이걸 모든 위치에서 진행하면 된다.

다른 풀이

이렇게 모든 경우를 다 그리다가 실수할 수도 있다.
--> 결국 현재 좌표에서 가능한 모든 그림을 확인할 수 있다면 해보는 것이 좋다.

그렇다면 DFS로 문제를 해결할 수 있을 것 같다.
주어진 테트리스 블럭의 모양을 보면 정사각형 4개를 인접하게 이어 붙여 나올 수 있는 모양이다.
이것을 보고 백트랙킹으로 문제를 해결할 수 있겠다고 느꼈어야했음

임의의 위치에서 테트리스 블럭 모양으로 확장하는 방법은... 지금까지 방문한 위치들을 탐색하면서 인접한 위치로 이동하여 한 칸씩 확장해 나가면 된다.

이때 인접한 위치로 이동하기 위해서는
1. 해당 영역이 격자 내부에 위치
2. 아직 방문 안함

import sys

sys.stdin = open("input.txt", "rt")

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

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

# ! 3가지에 대해서 모든 경우 구하기
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
max_sum = 0


def isInner(x, y):
    if 0 <= x < n and 0 <= y < m:
        return True
    return False


def can_go(x, y):
    global visited
    if isInner(x, y) and (x, y) not in visited:
        return True
    return False


def DFS(L, now_sum):
    global max_sum
    if L == 4:  # ! 4칸 확인
        max_sum = max(max_sum, now_sum)
    else:
        for (x, y) in visited:  # ! 인접한 좌표들로부터 꺼내야지 -> 즉 주어진 좌표에 대해 가능한 모든 모양을 탐색
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if can_go(nx,ny): # ! 해당 좌표 내부에 있으면서 아직 방문 안했으면
                    visited.append((nx,ny))
                    DFS(L+1, now_sum + g[nx][ny])
                    visited.pop()

visited = []
for x in range(n):
    for y in range(m):
        visited.append((x, y))  # ! 현재 좌표
        DFS(1, g[x][y])
        visited.pop()

print(max_sum)

위 코드와 같이 격자를 탐색하되 -> 현재 방문한 위치들을 탐색하면서 확장하는 방법도 생각해보자.