[Python] 14500 테트로미노

📌 문제

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

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

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

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

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

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

📌 입력

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

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

📌 출력

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

📌 문제 풀이

👨‍🏫 접근

브루트포스를 풀 때는 어느 정도 뇌를 놓고 푸는 게 좋을 것 같다.

문제를 풀기 전에 시간 복잡도를 가늠해보자면, 먼저 N * M의 맵이 필요하고 각 테트리스 조각이 19개가 있으며 4개의 조각으로 이루어졌기에 4개 조각 위치의 탐색 4번이 필요하다.

즉, 최대한으로 오래 걸린다고 할 때 500 * 500 * 19 * 4 = 19,000,000이다. 1초에 1억번 연산을 한다고 했을 때도 1초가 걸리지 않는다. 즉 브루트 포스로 탐색하기에 적절하다.

그래서 모든 테트리스 조각의 좌표를 나타내어 그 테트리스 조각을 순회하여 문제를 풀 수 있다.

import sys
input = sys.stdin.readline

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

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

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

ans = -1

for x in range(n):
    for y in range(m):
        for i, j in zip(dx, dy):
            cnt = 0
            a1, a2, a3, a4 = map(lambda k: k + x, i)
            b1, b2, b3, b4 = map(lambda k: k + y, j)
            if (0 <= a1 < n and 0 <= a2 < n and 0 <= a3 < n and 0 <= a4 < n) and (0 <= b1 < m and 0 <= b2 < m and 0 <= b3 < m and 0 <= b4 < m):
                cnt += graph[a1][b1] + graph[a2][b2] + graph[a3][b3] + graph[a4][b4]
                ans = max(ans, cnt)

print(ans)

위와 같을 때 pypy3로 제출하여 가까스로 통과를 할 수 있었다.

---

물론 이렇게 풀어도 좋지만, 다른 방법을 통해서도 풀이할 수 있다. 바로 DFS를 활용하는 것이다. 테트리스 조각을 만들 때 필요한 방향은 (0, 1), (1, 0), (-1, 0) (순서대로 오른쪽, 아래, 위) 이렇게 총 세 개 이다. 이렇게 세 개의 방향으로 이동하기만 하면 테트리스 조각을 만들 수 있다. 이 테트리스 조각을 만들 때 바로 깊이 우선 탐색을 실시하는 것이다. 직접 종이에 그려보면서 테트리스 조각을 만들면 모두 만들 수 있다.

이때, 깊이 우선 탐색이기 때문에 'ㅗ' 형상의 모양은 만들지 못해서 특정 조건을 하나 세워야 한다. 다음 좌표를 인자로 넣는 것이 아니라 현재 좌표를 인자로 넣는 것이다.

👨‍🏫 문제 풀이

📄 전체 코드

import sys
input = sys.stdin.readline

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

graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[0] * m for _ in range(n)]
move = [(0, 1), (1, 0), (-1, 0)]
ans, MAX = 0, max(map(max, graph))

def dfs(x, y, cnt, SUM):
    global ans
    if cnt == 0:
        ans = max(ans, SUM)
        return

    if ans >= SUM + cnt * MAX:
        return

    for i, j in move:
        nx = x + i
        ny = y + j
        if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
            visited[nx][ny] = 1
            if cnt == 2:
                dfs(x, y, cnt - 1, SUM + graph[nx][ny])
            dfs(nx, ny, cnt - 1, SUM + graph[nx][ny])
            visited[nx][ny] = 0

for i in range(n):
    for j in range(m):
        visited[i][j] = 1
        dfs(i, j, 3, graph[i][j])
        visited[i][j] = 0

print(ans)

📄 준비

input = sys.stdin.readline

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

graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[0] * m for _ in range(n)]
move = [(0, 1), (1, 0), (-1, 0)]
ans, MAX = 0, max(map(max, graph))

좌표를 저장해주고, 방문 테이블도 하나 만들어준다. 움직임은 우, 상, 하로 구현하기 위해 [(0, 1), (1, 0), (-1, 0)]을 저장한다. 답을 저장하고 출력하기 위해 ans 변수를 설정하고, 시간을 최소화 하기 위해서 MAX라는 변수도 만들었다.

📄 풀이

def dfs(x, y, cnt, SUM):
    global ans
    if cnt == 0:
        ans = max(ans, SUM)
        return

    if ans >= SUM + cnt * MAX:
        return

    for i, j in move:
        nx = x + i
        ny = y + j
        if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
            visited[nx][ny] = 1
            if cnt == 2:
                dfs(x, y, cnt - 1, SUM + graph[nx][ny])
            dfs(nx, ny, cnt - 1, SUM + graph[nx][ny])
            visited[nx][ny] = 0

for i in range(n):
    for j in range(m):
        visited[i][j] = 1
        dfs(i, j, 3, graph[i][j])
        visited[i][j] = 0

print(ans)

dfs의 매개변수를 설정한다. x좌표와 y좌표를 받고, 조각의 개수인 cnt, 그 조각에서의 점수 총 합을 담을 SUM으로 총 4개를 설정했다. 만약 cnt가 0이라면, 즉 테트리스 조각을 완성했다면 SUM과 ans 중에서 최댓값을 다시 저장한다.

이때, MAX를 사용하였는데 만약 여태 더했던 SUM과 나머지로 올 수 있는 최댓값인 cnt * MAX를 더했을 때보다 ans 값이 더 크거나 같으면 굳이 더 순회할 필요가 없으므로 return하여 쓸데없는 프로세스를 중단한다.

move를 순회하여서 그래프 내에 있을 때 방문처리하고 스스로를 호출한 다음 방문을 취소하여 다른 때의 함수의 실행에 영향이 없도록 한다. cnt가 2일 때 원래 좌표를 다시 인자로 넣은 이유는 'ㅗ' 모양을 만들기 위함이다.

이렇게 하여 n과 m 그래프 모두를 순회하면서 ans의 최댓값을 구하는 것이다.

📌 총평

이 문제로 브루트 포스가 진짜 무식하게 푸는 것이구나를 느낄 수 있어서 한결 맘이 편해졌다.