백준 14500번: 테트로미노 (python, 파이썬)

• 문제

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

• 정사각형은 서로 겹치면 안 된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

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

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

---

• 입력

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

---

• 출력

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

---

• 코드

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

maps = [list(map(int, input().split(' '))) for _ in range(n)]
check = [[True]*m for _ in range(n)]

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

# 재귀함수로 가능한 사각형
def go(x, y, now, cnt):
    global max_result
    
    # 정사각형이 4개가 되면 최대값과 비교하고 dfs 종료
    if cnt == 4:
        if now > max_result:
            max_result = now
        return

    for i in range(4):
        new_x = x + dx[i]
        new_y = y + dy[i]

        if 0 <= new_x < n and 0 <= new_y < m:
            if check[new_x][new_y]:
                check[new_x][new_y] = False
                go(new_x, new_y, now+maps[new_x][new_y], cnt+1)
                check[new_x][new_y] = True

# 재귀함수로 불가능한 사각형
def nogo(x, y):
    # 가운데 값 고정
    center = maps[x][y]
    
    # 상하좌우 날개
    wings = 4

    min_result = 100000

    for i in range(4):
        new_x = x + dx[i]
        new_y = y + dy[i]
        
        # 날개가 2개면 테트로미노를 만들지 못하므로 종료
        if wings == 2:
            return 0
        
        # 범위를 벗어난 경우 날개 1개 감소
        if new_x < 0 or new_x >= n or new_y < 0 or new_y >= m:
            wings -= 1
            continue
        
        # 범위를 벗어나지 않았다면 값을 더해주고 해당 값이 최소값인지 찾는다
        center += maps[new_x][new_y]
        if maps[new_x][new_y] < min_result:
            min_result = maps[new_x][new_y]
    
    # 날개가 4개의 경우 총 5개의 정사각형이므로 가장 최소값인 사각형 1개를 빼준다
    if wings == 4:
        center -= min_result

    return center


for i in range(n):
    for j in range(m):
        check[i][j] = False
        go(i, j, maps[i][j], 1)
        check[i][j] = True

        temp = nogo(i, j)
        if temp > max_result:
            max_result = temp

print(max_result)

노란색 사각형중에 최소값을 제거하면 dfs로 구현 못하는 테트로미노 사각형 최대값을 찾을 수 있다

---

• 출처

www.acmicpc.net/problem/14500