https://www.acmicpc.net/problem/12100
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
www.acmicpc.net
브루트포스문제라고 생각하며 재귀호출을 통해서 모든 경우의 수를 탐색한다.
매 move마다 check 배열을 생성해서 병합이 되어있는지 안되어있는지 검새를 해주는 것이 포인트 이다.
현재 자신의 위치와 다음 위치 모두가 병합된 적이 없어야만 병합을 시켜준다.
또한, 네가지 방향으로 움직이는 것에 대해서 이중포문의 range가 미묘하게 변한다.
따라서 하나의 형태로 처리해 주는 것 보다는 flag를 두어서 flag에 따라 다르게 동작하도록 move함수를 구성하는게 좋다.
|
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
|
from copy import deepcopy
def move(n, A, flag):
a = deepcopy(A)
if flag == 0: #UP
d = -1
check = [[False] * n for _ in range(n)]
for c in range(n):
for r in range(n):
if a[r][c] != 0:
while 0 <= r + d < n:
if a[r + d][c] == a[r][c] and not check[r + d][c] and not check[r][c]:
a[r + d][c] *= 2
check[r + d][c] = True
a[r][c] = 0
break
else:
if a[r + d][c] == 0:
a[r + d][c] = a[r][c]
a[r][c] = 0
r += d
elif flag == 1: #DOWN
d = 1
check = [[False] * n for _ in range(n)]
for c in range(n):
for r in range(n - 1, -1, -1):
if a[r][c] != 0:
while 0 <= r + d < n:
if a[r + d][c] == a[r][c] and not check[r + d][c] and not check[r][c]:
a[r + d][c] *= 2
check[r + d][c] = True
a[r][c] = 0
break
else:
if a[r + d][c] == 0:
a[r + d][c] = a[r][c]
a[r][c] = 0
r += d
elif flag == 2: #LEFT
d = -1
check = [[False] * n for _ in range(n)]
for r in range(n):
for c in range(n):
if a[r][c] != 0:
while 0 <= c + d < n:
if a[r][c] == a[r][c + d] and not check[r][c + d] and not check[r][c]:
a[r][c + d] *= 2
check[r][c + d] = True
a[r][c] = 0
break
else:
if a[r][c + d] == 0:
a[r][c + d] = a[r][c]
a[r][c] = 0
c += d
elif flag == 3: #RIGHT
d = 1
check = [[False] * n for _ in range(n)]
for r in range(n):
for c in range(n - 1, -1, -1):
if a[r][c] != 0:
while 0 <= c + d < n:
if a[r][c] == a[r][c + d] and not check[r][c + d] and not check[r][c]:
a[r][c + d] *= 2
check[r][c + d] = True
a[r][c] = 0
break
else:
if a[r][c + d] == 0:
a[r][c + d] = a[r][c]
a[r][c] = 0
c += d
return a
def recur(depth, a):
global trial, max_val, n
if depth == trial:
max_val = max(max_val, max(max(k) for k in a))
return
for i in range(4):
recur(depth+1, move(n, a, i))
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
trial = 5
max_val = 0
recur(0,a)
print(max_val)
|
cs |
728x90
반응형
'Problem Solving > BOJ' 카테고리의 다른 글
| [Python]13460. 구슬 탈출 2 (0) | 2019.05.10 |
|---|---|
| [Python]14502. 연구소 (0) | 2019.05.09 |
| [Python]1248. 맞춰봐 (0) | 2019.04.22 |
| [Python]14889. 스타트와 링크 (0) | 2019.04.22 |
| [Python]17143. 낚시왕 (0) | 2019.04.18 |
댓글