[Baekjoon] 14500 : 테트로미노 - Python

Gold5

14500번: 테트로미노

 

문제 풀이

 

풀이 1) 

 내가 떠올린 방법은 폴리노미노 도형들의 회전, 반전을 포함한 모든 경우 19가지를 리스트로 작성하고 가장 최대가 되는 값을 찾는 것이었다. 아마 가장 쉽게 떠올릴 수 있는 방법일 것이다. 

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

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

# 조각 넣는 법 19가지
my = [[1, 2, 3], [0, 0, 0],
      [1, 0, 1],
      [0, 0, 1], [1, 1, 1], [0, 0, 1], [-1, 0, 0], [0, 1, 2], [-2, -1, 0], [0, 1, 2], [1, 2, 2],
      [0, 1, 1], [-1, -1, 0], [1, 1, 2], [-1, 0, 1],
      [-1, 0, 0], [1, 1, 2], [-1, 0, 1], [0, 0, 1]]
mx = [[0, 0, 0], [1, 2, 3],
      [0, 1, 1],
      [1, 2, 2], [0, 1, 2], [1, 2, 0], [2, 1, 2], [1, 1, 1], [1, 1, 1], [1, 0, 0], [0, 0, 1],
      [1, 1, 2], [1, 2, 1], [0, 1, 1], [1, 1, 0],
      [1, 1, 2], [0, 1, 0], [1, 1, 1], [1, 2, 1]]

max_value = -1

def solution():
    global max_value

    for i in range(n):
        for j in range(m):
            # 조각 넣어보기
            for k in range(19):
                score = tetro_mino[i][j]
                for l in range(3):
                    nx = i + mx[k][l]
                    ny = j + my[k][l]
                    if 0<=nx<n and 0<=ny<m:
                        score += tetro_mino[nx][ny]
                max_value = max(max_value, score)

solution()
print(max_value)

하지만 이렇게 19가지를 모두 좌표로 적고 문제를 푸는 건 실수를 하기가 쉬울 것 같다. (쓰게 된다면 꼼꼼하게 확인하자) 

나같은 경우 x, y좌표를 헷갈려서 몇 가지를 틀리게 적었었다. 예제는 모두 정답이 나왔는데 실패가 떠서 한참 헤맸다 ㅎ..

 

그래서 좀 더 멋진 방법이 없을까해서 찾아보다가 배운.. 두 번째 풀이

어떻게 이런 생각을 할까? ㅠㅠ

 

풀이 2)

폴리노미노의 'ㅗ'를 제외한 모든 모양(회전, 반전 포함)은 특정 칸을 기준으로 4칸을 움직였을 때 나오는 모든 모양이다!

dfs를 이용해 4칸을 이동시키고 그 때의 값을 계산해 최대값과 비교해주면 된다. 

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

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

mx = [-1, 0, 1, 0]
my = [0, -1, 0, 1]
# 'ㅗ' 따로 계산
my_o = [[-1, 0, 0], [1, 1, 2], [-1, 0, 1], [0, 0, 1]]
mx_o = [[1, 1, 2], [0, 1, 0], [1, 1, 1], [1, 2, 1]]

game_board = [[0] * m for _ in range(n)]
max_value = -1

def dfs(num, score, x, y):
    global max_value
    if num == 4:
        max_value = max(max_value, score)
        return

    for i in range(4):
        nx = mx[i] + x
        ny = my[i] + y

        if 0 <= nx < n and 0 <= ny < m and game_board[nx][ny] == 0:
            game_board[nx][ny] = 1
            dfs(num+1, score + tetro_mino[nx][ny], nx, ny)
            game_board[nx][ny] = 0

def other(x, y):
    global max_value

    for i in range(4):
        score = tetro_mino[x][y]
        for j in range(3):
            nx = x + mx_o[i][j]
            ny = y + my_o[i][j]
            if 0 <= nx < n and 0 <= ny < m:
                score += tetro_mino[nx][ny]
            else:
                break
        max_value = max(max_value, score)

for i in range(n):
    for j in range(m):
        game_board[i][j] = 1
        dfs(1, tetro_mino[i][j], i, j)
        game_board[i][j] = 0

        other(i, j)

print(max_value)

 

내가 짠 코드는 Pypy로만 통과가 되고 Python에선 시간초과가 뜬다 ㅠ..

아직 뭐가 문젠진 모르겠지만.. 아래 블로그에는 최적화된 코드가 있어 참고하면 좋을 것 같다.

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