문제:
2048 게임은 4x4 크기의 보드에서 혼자 즐기는 게임이다.
이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 디시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)
이 문제에서 다루는 2048 게임은 보드의 크기가 NxN이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 쵣 5번 이동해서 만들 수 있는 가장 큰 불록의 값을 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 보드의 크기 N (1<=N<=20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
출력:
최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.
풀이방법:
최대 5번만 이동하면 되기 때문에 dfs를 사용해서 모든 경우를 탐색하고, 그 중 가장 최댓값을 찾아내도록 하면 된다.
반복문을 사용해서 상하좌우로 이동하게 만들었다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
import copy
def dfs(numbers,count):
global answer
if count==5:
if max(max(numbers,key=lambda x : max(x))) > answer:
answer = max(max(numbers,key=lambda x : max(x)))
return
count+=1
for i in range(4):
if i==0:
numberT = copy.deepcopy(numbers)
for j in range(N):
tmp = -1
temp = []
for num in numberT[j]:
if num == 0:
continue
if len(temp)==0:
temp.append(num)
tmp = num
else:
if tmp==num and temp[-1]==num:
temp[-1]=num*2
else:
temp.append(num)
tmp = num
if len(temp)!=N:
while len(temp)<N:
temp.append(0)
numberT[j]=temp
dfs(numberT,count)
if i==1:
numberT = copy.deepcopy(numbers)
for j in range(N):
tmp = -1
temp = []
for k in range(N-1,-1,-1):
if numberT[k][j]==0:
continue
if len(temp)==0:
temp.append(numberT[k][j])
tmp = numberT[k][j]
else:
if tmp == numberT[k][j] and temp[-1]==numberT[k][j]:
temp[-1]=numberT[k][j]*2
else:
temp.append(numberT[k][j])
tmp = numberT[k][j]
temp.reverse()
if len(temp)!=N:
while len(temp)<N:
temp.insert(0,0)
for k in range(N):
numberT[k][j]=temp[k]
dfs(numberT,count)
elif i==2:
numberT = copy.deepcopy(numbers)
for j in range(N):
tmp = -1
temp = []
for num in list(reversed(numberT[j])):
if num == 0:
continue
if len(temp)==0:
temp.append(num)
tmp = num
else:
if tmp == num and temp[-1]==num:
temp[-1]=num*2
else:
temp.append(num)
tmp = num
if len(temp)!=N:
while len(temp)<N:
temp.append(0)
numberT[j]=list(reversed(temp))
dfs(numberT,count)
elif i==3:
numberT = copy.deepcopy(numbers)
for j in range(N):
tmp = -1
temp = []
for k in range(N):
if numberT[k][j] == 0:
continue
if len(temp)==0:
temp.append(numberT[k][j])
tmp = numberT[k][j]
else:
if tmp == numberT[k][j] and temp[-1]==numberT[k][j]:
temp[-1]=numberT[k][j]*2
else:
temp.append(numberT[k][j])
tmp = numberT[k][j]
if len(temp)!=N:
while len(temp)<N:
temp.append(0)
for k in range(N):
numberT[k][j]=temp[k]
dfs(numberT,count)
N = int(input())
numbers = []
for _ in range(N):
numbers.append(list(map(int,input().split())))
answer = -1
count = 0
dfs(numbers,count)
print(answer)
|
cs |
문제링크:
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]19948. 음유시인 영재 (0) | 2020.10.15 |
|---|---|
| [BOJ]1644. 소수의 연속합 (0) | 2020.10.13 |
| [BOJ]1806 부분합 (0) | 2020.09.22 |
| [BOJ]2096. 내려가기 (0) | 2020.09.15 |
| [BOJ]10972. 다음 순열 (0) | 2020.09.10 |