문제
이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
출력
최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.
예제 입력 1
3
2 2 2
4 4 4
8 8 8
예제 출력 1
16
Concept
수행횟수가 최대 5번이고, 제자리, 위, 아래, 왼쪽, 오른쪽 총 5개 방향으로 움직일 수 있으므로 5x5x5x5x5 정도의 기본적인 연산이 필요하다. 물론 여기에 기본적인 행렬 조작을 위한 연산을 위한 시간이 추가되지만, brute force로 할만한 사이즈로 생각하여 직접 구현해보기로 했다.
Code
import copy
def run(arr, cnt):
global max
global n
if cnt>=5: # 최대 횟수인 5을 다채웠다면
# max보다 큰 원소가 있다면 max 업데이트
for row in range(n):
for col in range(n):
if (arr[row][col] > max):
max = arr[row][col]
return
for i in range(5):
run(move(i, arr), cnt+1)
def move(k, paramArr): # paramArr를 직접 바꾸지 않음!
arr = copy.deepcopy(paramArr)
global n
if (k==1): #위로
for col in range(n):
# 중간에 0은 아래로 보내고 시작하자.
rowIndex=0
for row in range(n):
if (arr[row][col] != 0):
arr[rowIndex][col] = arr[row][col]
rowIndex+=1
#나머지는 0으로.
for row in range(rowIndex, n):
arr[row][col] = 0
# 더하는 작업
for row in range(n-1):
if (arr[row][col] == arr[row+1][col]):
arr[row][col] += arr[row+1][col]
arr[row+1][col] = 0
# 다시 중간에 0은 아래로 보내고 시작하자.
rowIndex=0
for row in range(n):
if (arr[row][col] != 0):
arr[rowIndex][col] = arr[row][col]
rowIndex+=1
#나머지는 0으로.
for row in range(rowIndex, n):
arr[row][col] = 0
elif (k==2): #왼쪽으로
for row in range(n):
# 중간에 0은 오른쪽로 보내고 시작하자.
colIndex=0
for col in range(n):
if (arr[row][col] != 0):
arr[row][colIndex] = arr[row][col]
colIndex+=1
#나머지는 0으로.
for col in range(colIndex, n):
arr[row][col] = 0
# 더하는 작업
for col in range(n-1):
if (arr[row][col] == arr[row][col+1]):
arr[row][col] += arr[row][col+1]
arr[row][col+1] = 0
# 중간에 0은 오른쪽으로 보내고 시작하자.
colIndex=0
for col in range(n):
if (arr[row][col] != 0):
arr[row][colIndex] = arr[row][col]
colIndex+=1
#나머지는 0으로.
for col in range(colIndex, n):
arr[row][col] = 0
elif (k==3): # 오른쪽으로
for row in range(n):
# 중간에 0은 왼쪽으로 보내자
colIndex=n-1
for col in range(n-1, -1, -1): #오른쪽에서 왼쪽으로 접근해가며
if (arr[row][col] != 0):
arr[row][colIndex] = arr[row][col]
colIndex -= 1
# 나머지는 0으로.
for col in range(colIndex, -1, -1):
arr[row][col] = 0
# 더하기
for col in range(n-1, 0, -1):
if (arr[row][col] == arr[row][col-1]):
arr[row][col] += arr[row][col-1]
arr[row][col-1] = 0
# 다시 중간에 0은 왼쪽으로 보내자
colIndex=n-1
for col in range(n-1, -1, -1): #오른쪽에서 왼쪽으로 접근해가며
if (arr[row][col] != 0):
arr[row][colIndex] = arr[row][col]
colIndex -= 1
# 나머지는 0으로.
for col in range(colIndex, -1, -1):
arr[row][col] = 0
elif (k==4): #아래로
for col in range(n):
# 중간에 0 은 위로 보내고 시작
rowIndex = n-1
for row in range(n-1, -1, -1):
if (arr[row][col] != 0):
arr[rowIndex][col] = arr[row][col]
rowIndex -= 1
#나머지는 0
for row in range(rowIndex, -1, -1):
arr[row][col] =0
#더하는 작업
for row in range(n-1, 0, -1):
if (arr[row][col] == arr[row-1][col]):
arr[row][col] += arr[row-1][col]
arr[row-1][col] = 0
# 다시 중간에 0 은 위로 보내고 시작
rowIndex = n-1
for row in range(n-1, -1, -1):
if (arr[row][col] != 0):
arr[rowIndex][col] = arr[row][col]
rowIndex -= 1
#나머지는 0
for row in range(rowIndex, -1, -1):
arr[row][col] =0
return arr
n=int(input())
arr=[]
for i in range(n):
temp=list(map(int, input().split()))
arr.append(temp)
max=-1
run(arr, 0)
print(max)
import copy
def run(arr, cnt):
global max
global n
if cnt>=5: # 최대 횟수인 5을 다채웠다면
# max보다 큰 원소가 있다면 max 업데이트
for row in range(n):
for col in range(n):
if (arr[row][col] > max):
max = arr[row][col]
return
for i in range(5):
run(move(i, arr), cnt+1)
def move(k, paramArr): # paramArr를 직접 바꾸지 않음!
arr = copy.deepcopy(paramArr)
global n
if (k==1): #위로
for col in range(n):
# 중간에 0은 아래로 보내고 시작하자.
rowIndex=0
for row in range(n):
if (arr[row][col] != 0):
arr[rowIndex][col] = arr[row][col]
rowIndex+=1
#나머지는 0으로.
for row in range(rowIndex, n):
arr[row][col] = 0
# 더하는 작업
for row in range(n-1):
if (arr[row][col] == arr[row+1][col]):
arr[row][col] += arr[row+1][col]
arr[row+1][col] = 0
# 다시 중간에 0은 아래로 보내고 시작하자.
rowIndex=0
for row in range(n):
if (arr[row][col] != 0):
arr[rowIndex][col] = arr[row][col]
rowIndex+=1
#나머지는 0으로.
for row in range(rowIndex, n):
arr[row][col] = 0
elif (k==2): #왼쪽으로
for row in range(n):
# 중간에 0은 오른쪽로 보내고 시작하자.
colIndex=0
for col in range(n):
if (arr[row][col] != 0):
arr[row][colIndex] = arr[row][col]
colIndex+=1
#나머지는 0으로.
for col in range(colIndex, n):
arr[row][col] = 0
# 더하는 작업
for col in range(n-1):
if (arr[row][col] == arr[row][col+1]):
arr[row][col] += arr[row][col+1]
arr[row][col+1] = 0
# 중간에 0은 오른쪽으로 보내고 시작하자.
colIndex=0
for col in range(n):
if (arr[row][col] != 0):
arr[row][colIndex] = arr[row][col]
colIndex+=1
#나머지는 0으로.
for col in range(colIndex, n):
arr[row][col] = 0
elif (k==3): # 오른쪽으로
for row in range(n):
# 중간에 0은 왼쪽으로 보내자
colIndex=n-1
for col in range(n-1, -1, -1): #오른쪽에서 왼쪽으로 접근해가며
if (arr[row][col] != 0):
arr[row][colIndex] = arr[row][col]
colIndex -= 1
# 나머지는 0으로.
for col in range(colIndex, -1, -1):
arr[row][col] = 0
# 더하기
for col in range(n-1, 0, -1):
if (arr[row][col] == arr[row][col-1]):
arr[row][col] += arr[row][col-1]
arr[row][col-1] = 0
# 다시 중간에 0은 왼쪽으로 보내자
colIndex=n-1
for col in range(n-1, -1, -1): #오른쪽에서 왼쪽으로 접근해가며
if (arr[row][col] != 0):
arr[row][colIndex] = arr[row][col]
colIndex -= 1
# 나머지는 0으로.
for col in range(colIndex, -1, -1):
arr[row][col] = 0
elif (k==4): #아래로
for col in range(n):
# 중간에 0 은 위로 보내고 시작
rowIndex = n-1
for row in range(n-1, -1, -1):
if (arr[row][col] != 0):
arr[rowIndex][col] = arr[row][col]
rowIndex -= 1
#나머지는 0
for row in range(rowIndex, -1, -1):
arr[row][col] =0
#더하는 작업
for row in range(n-1, 0, -1):
if (arr[row][col] == arr[row-1][col]):
arr[row][col] += arr[row-1][col]
arr[row-1][col] = 0
# 다시 중간에 0 은 위로 보내고 시작
rowIndex = n-1
for row in range(n-1, -1, -1):
if (arr[row][col] != 0):
arr[rowIndex][col] = arr[row][col]
rowIndex -= 1
#나머지는 0
for row in range(rowIndex, -1, -1):
arr[row][col] =0
return arr
print("xxx")
n=int(input())
arr=[]
for i in range(n):
temp=list(map(int, input().split()))
arr.append(temp)
max=-1
run(arr, 0)
print(max)
Comment
압도적인 사이즈의 코드이다.
하지만 생~각했던 것 보다는 할만했고, 한번에 통과하여 나름 깔끔하단 생각이 들었던 문제.
deprecated