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

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

14500번: 테트로미노

문제 설명

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

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

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

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

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

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

---

풀이 과정

이 문제는 푸는 방법이 다양하다.

DFS를 이용해 푸는 방법도 있고, 직접 테트리스 모형을 모두 고려하여 하나하나 확인해주는 방법도 있다.

 

DFS를 이용한 풀이는 깔끔하다는 장점이 있지만 시간이 좀 더 오래걸린다는 단점이 있고

직접 테트리스 모형을 만드는 풀이는 시간이 빠르다는 장점이 있지만, 구현이 조금 지저분하다는 단점이 있다.

 

시간을 고려한다면 직접 만드는 풀이가 좋을 것이며,

깔끔한 풀이를 고려한다면 DFS 풀이가 좋을 것 같다.

 

그래서 두 방법 모두 풀어보았다.

 

① 먼저 DFS를 이용한 풀이는 백트래킹을 이용해 맵의 처음부터 끝칸까지 모든 칸에 대해 DFS를 수행한다.

한 칸에서 DFS를 수행하게 되면 모든 테트리스 모형을 확인할 수가 있다.

예를 들어, 쭉 오른쪽으로 간다면 ㅡ 모양이 될 것이고

오른쪽으로 갔다 아래로 갔다 왼쪽으로 가면 ㅁ 모양이 완성될 것이다.

 

하지만 ㅗ 모양이 DFS로 완성할 수 없기 때문에

depth = 1일 때, 즉 2칸까지 완성했을 때 칸을 다음칸으로 옮기지 않은 그대로인 상태에서

DFS를 수행함으로써 ㅗ 모양을 만들 수 있다.

 

1번 풀이를 이용한 코드는 다음과 같다.

n, m = map(int, input().split())
board = []
visited = [[False] * m for _ in range(n)]

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

for i in range(n):
    board.append(list(map(int, input().split())))

answer = 0

def dfs(x, y, mysum, depth):
    global answer

    if depth == 3:
        answer = max(answer, mysum)
        return
    else:
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m or visited[nx][ny]:
                continue

            if depth == 1:  # ㅗ 모양은 DFS로 만들 수 없으므로 예외처리
                visited[nx][ny] = True
                dfs(x, y, mysum + board[nx][ny], depth + 1)
                visited[nx][ny] = False

            visited[nx][ny] = True
            dfs(nx, ny, mysum + board[nx][ny], depth + 1)
            visited[nx][ny] = False


for i in range(n):
    for j in range(m):
        visited[i][j] = True
        dfs(i, j, board[i][j], 0)
        visited[i][j] = False

print(answer)

 

② 테트리스 모형을 모두 배열로 만들어서 비교한다.

첫 칸부터 끝칸까지 모든 칸에 대해 테트리스 모형을 대입하여 최댓값을 비교해나가는 방식이다.

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

tetris = [
    [(0, 0), (0, 1), (1, 0), (1, 1)], # ㅡ
    [(0, 0), (0, 1), (0, 2), (0, 3)], # ㅣ
    [(0, 0), (1, 0), (2, 0), (3, 0)], # ㅁ
    [(0, 0), (1, 0), (1, 1), (2, 1)], # h
    [(1, 0), (0, 1), (1, 1), (2, 0)], # h 회전
    [(1, 0), (1, 1), (0, 1), (0, 2)], # ...
    [(0, 0), (0, 1), (1, 1), (1, 2)],
    [(0, 0), (1, 0), (2, 0), (2, 1)], # L
    [(0, 1), (1, 1), (2, 0), (2, 1)], # ...
    [(0, 0), (0, 1), (1, 0), (2, 0)],
    [(0, 0), (0, 1), (1, 1), (2, 1)],
    [(1, 0), (0, 1), (1, 1), (1, 2)],
    [(0, 0), (0, 1), (0, 2), (1, 1)],
    [(0, 0), (1, 0), (1, 1), (1, 2)],
    [(1, 0), (1, 1), (1, 2), (0, 2)],
    [(0, 0), (0, 1), (0, 2), (1, 0)],
    [(0, 0), (0, 1), (0, 2), (1, 2)],
    [(0, 0), (1, 0), (1, 1), (2, 0)],
    [(1, 0), (0, 1), (1, 1), (2, 1)] # ㅓ
]

def solution(x, y):
    global answer
    for i in range(19):
        tmp = 0
        for j in range(4):
            nx = x + tetris[i][j][0]
            ny = y + tetris[i][j][1]

            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                break

            tmp += board[nx][ny]

        answer = max(answer, tmp)

answer = 0
for i in range(n):
    for j in range(m):
        solution(i, j)

print(answer)

 

③ 마찬가지로 모든 테트리스칸에 대해 수행하는 방법이지만

배열에 모두 기입하는 것이 아닌 함수로 하나씩 만들어 대입하는 방법이다.

 

수행시간은 이 풀이가 가장 짧았다.

하지만 구현해야 하는 코드의 길이가 상당히 긴 단점이 있다.

n, m = map(int,input().split())
graph = []
ans = 0

def shape1(i, j): # ㅡ
    if j+3 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i][j+2] + graph[i][j+3]

def shape2(i, j): # ㅣ
    if i+3 >= n:
        return 0
    return graph[i][j] + graph[i+1][j] + graph[i+2][j] + graph[i+3][j]

def shape3(i, j): # L모양
    if i+2 >= n or j+1 >= m:
        return 0
    return graph[i][j] + graph[i+1][j] + graph[i+2][j] + graph[i+2][j+1]

def shape4(i, j): # L모양 대칭
    if i+2 >= n or j-1 < 0:
        return 0
    return graph[i][j] + graph[i+1][j] + graph[i+2][j] + graph[i+2][j-1]

def shape5(i, j): # L모양 시계방향 회전
    if i-1 < 0 or j+2 >= m:
        return 0
    return graph[i][j] + graph[i-1][j] + graph[i-1][j+1] + graph[i-1][j+2]

def shape6(i, j): # L대칭 시계방향 회전
    if i+1 >= n or j+2 >=m:
        return 0
    return graph[i][j] + graph[i+1][j] + graph[i+1][j+1] + graph[i+1][j+2]

def shape7(i, j): # L 시계방향 회전x2
    if i+2 >= n or j+1 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i+1][j+1] + graph[i+2][j+1]

def shape8(i, j): # L대칭 시계방향 회전x2
    if i+2 >= n or j+1 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i+1][j] + graph[i+2][j]

def shape9(i, j): # L 시계방향 회전x3
    if i-1 < 0 or j+2 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i][j+2] + graph[i-1][j+2]

def shape10(i, j): # L대칭 시계방향 회전x3
    if i+1 >= n or j+2 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i][j+2] + graph[i+1][j+2]

def shape11(i, j): # ㅁ모양
    if i+1 >= n or j+1 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i+1][j] + graph[i+1][j+1]

def shape12(i, j): # 번개모양
    if i+2 >= n or j+1 >= m:
        return 0
    return graph[i][j] + graph[i+1][j] + graph[i+1][j+1] + graph[i+2][j+1]

def shape13(i, j): # 번개모양 회전
    if i-1 < 0 or j+2 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i-1][j+1] + graph[i-1][j+2]

def shape14(i, j): #번개모양 대칭
    if i+2 >= n or j-1 < 0:
        return 0
    return graph[i][j] + graph[i+1][j] + graph[i+1][j-1] + graph[i+2][j-1]

def shape15(i, j): #번개모양 대칭 회전
    if i+1 >= n or j+2 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i+1][j+1] + graph[i+1][j+2]

def shape16(i, j): #ㅗ모양
    if i-1 < 0 or j+2 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i-1][j+1] + graph[i][j+2]

def shape17(i, j): #ㅗ모양 회전
    if i+2 >= n or j+1 >= m:
        return 0
    return graph[i][j] + graph[i+1][j] + graph[i+1][j+1] + graph[i+2][j]

def shape18(i, j): #ㅗ모양 회전x2
    if i+1 >= n or j+2 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i+1][j+1] + graph[i][j+2]

def shape19(i, j): #ㅗ모양 회전x3
    if i+2 >= n or j-1 < 0:
        return 0
    return graph[i][j] + graph[i+1][j] + graph[i+1][j-1] + graph[i+2][j]


for i in range(n):
    graph.append(list(map(int,input().split())))

for i in range(n):
    for j in range(m):
        ans = max(ans, shape1(i,j), shape2(i,j), shape3(i,j), shape4(i,j), shape5(i,j), shape6(i,j), shape7(i,j), shape8(i,j), shape9(i,j),
                  shape10(i,j), shape11(i,j), shape12(i,j), shape13(i,j), shape14(i,j), shape15(i,j), shape16(i,j), shape17(i,j), shape18(i,j), shape19(i,j))

print(ans)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !