BOJ: 12100

Posted on In

문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.
이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)
이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

Solution

해당 문제를 풀기 위해서 크게 두가지로 나눌 수 있다고 생각했다.

  1. 2048 게임 시뮬레이션 함수 구현
    • 상, 하, 좌, 우를 입력받아 행렬의 각 요소를 이동
    • 해당 이동 시 1칸 단위로 틱을 나눠 이동 -> 합쳐지는 것의 우선순위를 고려하기 위해
    • 이동 방향에 따른 우선순위 고려 필수
  2. 브루트포스 구현을 통한 5번의 이동 후 최대 크기의 블록 탐색

해당 과정을 위해 먼저 simulation(dir) 함수를 개발하였다.
dir (0, 1, 2, 3)을 통해 우, 상, 좌, 하의 순서로 방향을 생각하고 개발하였다.
simulation(dir) 함수는 단순히 방향을 입력하면 해당 방향의 역순 (이동 방향에 따른 우선순위)으로 n2n(i, j, dir)을 실행시키는 함수이다.
n2n(i, j, dir)은 특정 블록의 좌표 (i, j)를 입력하면 방향 (dir)으로 이동하는 함수이다.
이동 방향으로의 블록이 현재 블록과 같고, 합쳐진 이력이 없으면 두 블록을 병합하고 현재 블록은 초기화하고 병합 이력을 기입하기 위해 visited 변수에 True로 입력한다.
이동 방향으로의 블록이 0인 경우 현재 블록과 바꿔주어 이동하며 현재 좌표를 진행방향으로 이동시킨다.
최종적으로 최대 5번의 이동 후 최댓값을 출력해야하므로 모든 경우의 수를 itertools.product로 수행한다. (블록의 값은 감소할 수 없기 때문)

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
import sys
import copy
from itertools import product
read = sys.stdin.readline

N = int(read())
sav = [[0 for _ in range(N)] for _ in range(N)]

for i in range(N):
  sav[i] = list(map(int, read().split()))

def n2n(i, j, dir):
  while True:
    if not (((0 <= i < N) and (0 <= j < N)) and ((0 <= i + dir[1] < N) and (0 <= j + dir[0] < N))):
      break
    elif not G[i][j] == 0:
      if G[i + dir[1]][j + dir[0]] == G[i][j] and not visited[i + dir[1]][j + dir[0]]:
        G[i + dir[1]][j + dir[0]] = G[i][j] * 2
        G[i][j] = 0
        visited[i + dir[1]][j + dir[0]] = True
        break
      elif G[i + dir[1]][j + dir[0]] == 0:
        G[i + dir[1]][j + dir[0]] = G[i][j]
        G[i][j] = 0
        i, j = i + dir[1], j + dir[0]
      else:
        break
    else:
      break

dir_t = ((1, 0), (0, -1), (-1, 0), (0, 1))
x_r = ((N - 2, -1, -1), (0, N, 1), (1, N, 1), (0, N, 1))
y_r = ((0, N, 1), (1, N, 1), (0, N, 1), (N - 2, -1, -1))

def simulation(dir): # 0, 1, 2, 3
  dir_x, dir_y = dir_t[dir]
  for i in range(y_r[dir][0], y_r[dir][1], y_r[dir][2]):
    for j in range(x_r[dir][0], x_r[dir][1], x_r[dir][2]):
      n2n(i, j, dir_t[dir])

res = 0

for a, b, c, d, e in product(range(4), range(4), range(4), range(4), range(4)):
  G = copy.deepcopy(sav)
  visited = [[False for _ in range(N)] for _ in range(N)]
  simulation(a)
  visited = [[False for _ in range(N)] for _ in range(N)]
  simulation(b)
  visited = [[False for _ in range(N)] for _ in range(N)]
  simulation(c)
  visited = [[False for _ in range(N)] for _ in range(N)]
  simulation(d)
  visited = [[False for _ in range(N)] for _ in range(N)]
  simulation(e)
  res = max(max(map(max, G)), res)
print(res)

Used Test Case

Case 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
'''
4
0 0 2 0
0 0 0 0
2 0 0 0
0 0 0 0
'''

simulation(1)

'''
[2, 0, 2, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
'''

Case 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
'''
4
0 0 2 0
0 0 0 0
2 0 0 0
0 0 0 0
'''

simulation(1)
simulation(2)

'''
[4, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
'''

Case 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
'''
4
4 2 0 0
0 0 0 0
0 0 0 0
2 0 0 0
'''

simulation(0)
simulation(1)
simulation(0)

'''
[4, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
'''

Case 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
'''
4
2 0 2 8
0 0 2 2
0 0 0 0
0 0 0 0
'''

simulation(2)

'''
[4, 8, 0, 0]
[4, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
'''

Case 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
'''
4
2 0 0 0
2 2 0 0
2 0 0 0
0 0 0 0
'''

simulation(1)

'''
[4, 2, 0, 0]
[2, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
'''

Case 6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
'''
4
2 4 16 8
8 4 0 0
16 8 2 0
2 8 2 0
'''

simulation(1)

'''
[2, 8, 16, 8]
[8, 16, 4, 0]
[16, 0, 0, 0]
[2, 0, 0, 0]
'''

Case 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
'''
4
2 4 8 2
2 4 0 0
2 0 0 0
2 0 2 0
'''

simulation(1)

'''
[4, 8, 8, 2]
[4, 0, 2, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
'''