[백준] 14500. 테트로미노/Python - Gold4

❓문제

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

성능 요약

메모리: 114816 KB, 시간: 152 ms

분류

구현, 브루트포스 알고리즘

 

문제 설명

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

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

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

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

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

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

✍🏻풀이

DFS와 백트래킹으로 접근하면 된다. 깊이 우선 탐색을 하면 ㅗ 모양을 제외한 모든 모양을 구할 수 있다.

ㅗ 모양을 만드려면 한 좌표에서 양 옆으로 탐색해야 한다. 그러나 보통 DFS를 풀 때 이전 좌표를 기록하지 않는다. 그러므로 좌표를 기록하여 이미 지나온 좌표더라도 다른 방향으로 탐색하여 ㅗ 모양을 만들면 된다.

https://jominseoo.tistory.com/96

[삼성 SW 역량테스트 기출] 백준 14500번 테트로미노(Python)

가지치기와 ㅗ모양에 대해서는 위 사이트를 참고해서 풀었다.

💻코드

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
visited = [[0 for _ in range(M)] for _ in range(N)]
mx = max(map(max, board))

def backtracking(pos, cnt, res):
    global ans
    if res + (4-cnt) * mx <= ans:
        return

    if cnt == 4:
        ans = max(res, ans)
        return

    for y, x in pos:
        for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            ny, nx = y + dy, x + dx
            if 0 <= ny < N and 0 <= nx < M and not visited[ny][nx]:
                visited[ny][nx] = 1
                backtracking(pos + [(ny, nx)], cnt + 1, res + board[ny][nx])
                visited[ny][nx] = 0

ans = 0
for y in range(N):
    for x in range(M):
        visited[y][x] = 1
        backtracking([(y, x)], 1, board[y][x])

print(ans)

📍후기

처음에 DFS로 풀었지만 ㅗ 모양을 해결하는 것에서 많은 시간을 소요했지만 이 문제를 풀면서 DFS에 대한 편협적인 생각을 깰 수 있었다고 생각한다.