> 파이썬, 구현, 브루트포스 알고리즘, 시뮬레이션, 백트래킹
📖 문제 : 2048(Easy) (Python)
2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.
이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)
<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.
<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.
<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.
<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다.
<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.
이 문제에서 다루는 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
내 코드
from collections import deque
from copy import deepcopy
N = int(input())
input_board = [list(map(int, input().split())) for _ in range(N)]
result = 0
def move(direction, board):
# top
if direction == 0:
for x in range(N):
not_zero = []
for y in range(N):
# 세로로 한줄씩 읽어가며 0이 아닌 값을 not_zero 리스트에 넣어줍니다.
if board[y][x] != 0:
not_zero.append(board[y][x])
idx = 0
not_zero = deque(not_zero)
while not_zero: # 0이 아닌 값이 있다면 합쳐줘야할 값이 있으므로,
if len(not_zero) == 1:
board[idx][x] = not_zero.popleft()
else:
# 합쳐지는 수는 2개 이므로 두 개를 popleft합니다.
a, b = not_zero.popleft(), not_zero.popleft()
# 만약 그 두개의 수가 같다면
if a == b:
# board에 업데이트를 해줍니다.
board[idx][x] = a + b
else: # 만약 그 두 개의 수가 다르다면
# 두 개의 수 중 앞에 있는 값은 다른 수와 합쳐질 기회가 없으므로 앞의 수만 board에 업데이트를 해줍니다.
board[idx][x] = a
# 두 개의 수 중 뒤의 수는 그 다음 수와 합칠 기회가 있으므로 다시 넣어줍니다.
not_zero.appendleft(b)
# 업데이트할 board의 idx값을 + 1 해줍니다.
idx += 1
# 가능한 모든 값을 합치고, 또 합쳐지지 못한 수도 다 board에 업데이트가 되었으므로,
# 그 뒤의 값은 0으로 채워줍니다.
for y in range(idx, N):
board[y][x] = 0
# down
elif direction == 1:
for x in range(N):
not_zero = []
for y in range(N - 1, -1, -1):
if board[y][x] != 0:
not_zero.append(board[y][x])
idx = N - 1
not_zero = deque(not_zero)
while not_zero:
if len(not_zero) == 1:
board[idx][x] = not_zero.popleft()
else:
a, b = not_zero.popleft(), not_zero.popleft()
if a == b:
board[idx][x] = a + b
else:
board[idx][x] = a
not_zero.appendleft(b)
idx -= 1
for y in range(idx, -1, -1):
board[y][x] = 0
# left
elif direction == 2:
for x in range(N):
not_zero = []
for y in range(N):
if board[x][y] != 0:
not_zero.append(board[x][y])
idx = 0
not_zero = deque(not_zero)
while not_zero:
if len(not_zero) == 1:
board[x][idx] = not_zero.popleft()
else:
a, b = not_zero.popleft(), not_zero.popleft()
if a == b:
board[x][idx] = a + b
else:
board[x][idx] = a
not_zero.appendleft(b)
idx += 1
for y in range(idx, N):
board[x][y] = 0
# right
else:
for x in range(N):
not_zero = []
for y in range(N - 1, -1, -1):
if board[x][y] != 0:
not_zero.append(board[x][y])
idx = N - 1
not_zero = deque(not_zero)
while not_zero:
if len(not_zero) == 1:
board[x][idx] = not_zero.popleft()
else:
a, b = not_zero.popleft(), not_zero.popleft()
if a == b:
board[x][idx] = a + b
else:
board[x][idx] = a
not_zero.appendleft(b)
idx -= 1
for y in range(idx, -1, -1):
board[x][y] = 0
return board
def DFS(board, cnt):
global result
# board를 움직일 수 있는 건 최대 5번 이므로, cnt = 5일 때, return 해줍니다.
if cnt == 5:
for i in range(N):
for j in range(N):
result = max(result, board[i][j])
return
# 위, 아래, 왼쪽, 오른쪽 4방향 움직일 수 있기 때문에
for i in range(4):
# 각각 처음 board를 바꾸면 안되기 때문에, deepcopy를 사용하여 리스트를 복사하여 줍니다.
temp_board = move(i, deepcopy(board))
DFS(temp_board, cnt + 1)
DFS(input_board, 0)
print(result)
Point ! ⭐️
- 이 문제에서 가장 고민을 많이 했던 것은 move함수보다 DFS 함수를 구현하는 것이였다.
사실 move함수도 빡쎘음 .. 😅
temp_board = move(i, deepcopy(board))
DFS(temp_board, cnt+1)
이 부분이 DFS함수의 매개변수 board를 deepcopy하여 move함수에게 인자로 전달하여 return 받은 board를 다시 DFS의 매개변수로 전달하는 과정이 어려웠다. 적기만해도 숨막히는 기분 🫢 ! 샬라샬라
그리고 move함수 안에 up, down, left, right를 나눈 것이아니라
처음에는 move_up, move_down, move_left, move_right 이런식으로 함수를 4개로 나누다보니 더 헷갈렸다.
직관적이라고 함수를 다 만들다가 더 어려워져버렸다.
그래서 DFS부분만 살짝 보고 move로 통합하여 호출하는 방식으로 바꿨다.
삼성 문제 풀어보니 거의 백트래킹, 구현, 시뮬레이션인 것 같다 !
감잡는 그 날 까지 !!
그 날이 이번주 주일 전까지어야하는데 ,,
그렇기 때문에 열심히 해보겠어 !!!!!!!!!!!!!!!!!!!!!!!!!!! - 풀이시간⏰ : 2시간 30분
백준
https://www.acmicpc.net/problem/12100
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
'SAMSUNG > 삼성 SW 역량 테스트 준비' 카테고리의 다른 글
| 순열과 조합 (직접 구현 & itertools 라이브러리) (0) | 2023.10.13 |
|---|---|
| [백준 20055번] 컨베이어 벨트 위의 로봇 (Python) (0) | 2023.10.12 |
| [백준 14891번] 톱니바퀴 (Python) (4) | 2023.08.04 |
| [백준 15686번] 치킨 배달 (Python) (함수 abs를 사용하여 절댓값 구하기, combinations로 조합 구하기) (0) | 2023.07.07 |
| [백준 14502번] 연구소 (Python) (combinations를 사용하여 조합, 깊은 복사, count함수로 카운트 하기) (0) | 2023.07.07 |