한번에 움직일수있는 경우의 수는 위 아래 왼쪽 4가지이므로 총 나올수 있는 모든 경우의 수는 4^5==1024개 입니다.
1024개의 경우만 체크하면 되고, 보드의 크기또한 최대가 20x20이기 때문에
모든 경우의 수를 일일이 체크해도 시간내에 충분히 답을 얻을수 있다고 생각했습니다.
그리고 남은건 2048게임을 구현하는거 뿐인데,
먼저 저는 2차원 배열인 게임 맵을 작은단위로 2번 나눠 1차원 배열을 왼쪽으로 미는 함수를 만들었습니다.
이 함수를 구현하는건 그냥 for만 써서 구현해도 되고 다른 방법을 써도 되겠지만, 제가 썼던 방법은 자료구조 큐입니다.
제가 왜 큐를 썼나면 예를들어서 한 라인이 4 4 8 8 라면 한번 합쳐진 숫자들은 다시는 합쳐질수 없기 때문에 왼쪽으로 밀고 나온 결과는 8 16 0 0 이 되어야 하는데
처음에는 이걸 어떻게 구현할까 고민하다가 최근에 프로그래머스에서 큐로 풀었던 문제가 생각났습니다.
그래서 한 라인을 전부 큐에 넣은뒤에, 큐가 빌때까지 왼쪽부터 자리를 채워나가면서 큐의 숫자를 빼주면 되겠다고 생각했습니다.
그래서 그걸 그대로 구현한게 이 함수입니다
from collections import deque
def slideLineToLeft(line: list):
l = len(line)
# 0은 빈공간이기 때문에 큐에 넣지않음
que = deque([ele for ele in line if ele != 0])
result = [0] * l
for i in range(l):
if not que: break
result[i] = que.popleft()
if not que: break
if result[i] == que[0]:
result[i] += que.popleft()
return result
큐를 써서 정말 간단하게 왼쪽으로 1차원 배열을 미는 함수 구현이 끝났습니다.
다음은 게임판을 왼쪽으로 미는 함수를 만들어야하는데, 이 slideLineToLeft를 2차원 배열속 모든 1차원 배열에 적용해주기만 하면 됩니다
def slideMatrixToLeft(matrix: list):
return [slideLineToLeft(line) for line in matrix]
이렇게 게임판을 왼쪽으로 미는 함수또한 첫번째 함수를 이용해 쉽게 만들어졌습니다
사실 게임판은 상하좌우로 밀어야하는데, 아직까진 왼쪽으로 미는 함수만 구현한 상태에요
그래서 게임판을 위,아래,오른쪽으로 미는 함수는
게임판을 오른쪽으로 90도씩 회전한다음 왼쪽으로 밀어주고 다시 360도가 돌만큼 오른쪽으로 돌려서
def slide(matrix, direction=0):
# direction 0 1 2 3==순서대로 왼쪽 아래 오른쪽 위 방향으로 슬라이드
# 오른쪽으로 90도씩 0 1 2 3 번 돌림
for _ in range(direction):
matrix = rotateMatrixRight(matrix)
# 슬라이드 하는 방향을 바꾸지 않고 상하좌우로 슬라이드 하기위해
# 오른쪽으로 0 90 180 270도 돌아간 행렬을 왼쪽으로 슬라이드함
result = slideMatrixToLeft(matrix)
# 4-오른쪽으로 돌린횟수만큼 돌려서 360(0)도 돌아간 상태로 원상복귀
for _ in range(4 - direction):
result = rotateMatrixRight(result)
return result
이것도 위에 함수를 만들어놔서 짧게 끝났습니다
이제 1024개의 경우들을 시험하면서 그 경우의 수들중에 가장 높았던 게임의 수를 찾아 출력하면 끝이에요!
def getMaxInMatrix(matrix: list):
return max(map(max, matrix))
n = int(input())
matrix = [list(map(int, input().split())) for i in range(n)]
result = 0
for a in range(4):
for b in range(4):
for c in range(4):
for d in range(4):
for e in range(4):
copy = matrix[:]
copy=slide(copy, a)
copy=slide(copy, b)
copy=slide(copy, c)
copy=slide(copy, d)
copy=slide(copy, e)
result=max(getMaxInMatrix(copy),result)
마지막엔 5중 반복문을 통해 각 경우의 최대값들을 저장해 끝냈습니다
근데 지금보니까 만약에 5번이 아니라 더 여러번 반복해야 했다면 이것도 재귀함수로 bfs를 했어야 될거같네요
