12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
이 문제는 2048 게임을 구현하는 문제입니다!
보드의 크기는 4X4이며 최대 5번 움직였을 때 보드판 내의 가장 큰 수를 구하는 게 목적입니다.
저는 해당 문제를 한 번에 통과를 못하였고 반례를 통해 코드를 보완한 후 통과를 했습니다..ㅎㅎ
혹시 코드를 짠 후 통과를 못하시는 분이 계시다면 반례를 통해 코드를 점검하는 것도 좋을 거 같아요😁
제가 참고한 반례 링크는 아래와 같습니다.
링크: www.acmicpc.net/board/view/50764
이 문제를 처음 읽고 나서 어떤 방향으로 먼저 움직여야 하나 고민이 많았습니다.
고민 끝에 결국 '다 해보자!'라는 생각이 들었고 문제 해결을 위한 가설은 아래와 같습니다.
가설: 분기점마다 모든 방향으로 움직이고 1) 최대 5번 움직이거나 2) 움직임 후의 변화가 없을 때 보드 안의 최대 값을 구하자
위 가설을 시도하기 위해 아래와 생각의 과정은 아래와 같습니다.
1. 입력된 숫자를 2의 제곱 꼴로 변경 후 지수 부분을 배열에 저장
2. N(=보드의 크기)에 따라 다음 행동 결정
2.1 만약 N == 1이라면 현재 보드의 최댓값을 바로 출력
2.2 N > 1이면 BFS 방식으로 탐색 시작
3. 현재 상태에서 상하좌우로 보드를 움직여서 보드 내의 블록 들을 계산
3.1 만약 계산 후 보드에 변화가 없다면 탐색을 멈추고 현재까지의 최댓값과 보드 내의 최댓값을 비교 후 저장
3.2 만약 계산 후 보드에 변화가 있다면 Queue에 현재 움직임 횟수와 보드의 상태를 저장
4. Queue가 빌 때까지 과정 3을 반복
5. 최댓값 출력
* 저는 1번 과정에서 리스트에 지수 부분만을 저장했지만 꼭 이렇게 하지 않고 숫자 그대로 저장해도 됩니다!
저는 이 문제를 처음 풀 때 두 가지 실수를 했습니다..!
1. 리스트의 깊은 복사를 고려하지 못했다.
=> 리스트의 경우(특히 2차원 이상)는 다른 변수에 저장할 때 주의를 해야 합니다
=> Python에서는 얕은 복사, 깊은 복사의 개념이 있으며 이 문제에서는 깊은 복사를 수행해야 합니다.
=> 깊은 복사는 deepcopy 메서드를 통해 수행 가능합니다!
2. 문제의 조건을 잘못 이해했다.
=> 제가 잘못 이해한 부분은 '다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다.' 이 부분입니다!
=> 저는 처음에 아래와 같은 오해를 했습니다.
ex) 보드를 왼쪽으로 기울였을 때
기울기 전 상태: 8 4 4 16
기울기 후 상태: 32 0 0 0 ----(X)
실제 (X)는 잘못된 계산이면 올바른 계산은 아래와 같습니다
기울 기 후 상태: 8 8 16 0
혹시 이 문제를 새로 푸시는 분들은 저와 같은 실수를 안 하시길 바랍니다😊
전체 코드
from collections import deque
import sys
from copy import deepcopy
def move(m, d):
mat = deepcopy(m)
isChanged = False
checkMat = [ [False] * N for _ in range(N)]
if d == "l":
for i in range(N):
for j in range(1, N):
if mat[i][j] == 0:
continue
while j > 0:
if mat[i][j-1] == 0:
mat[i][j-1] = mat[i][j]
mat[i][j] = 0
isChanged = True
j -= 1
elif mat[i][j-1] == mat[i][j]:
if checkMat[i][j-1] or checkMat[i][j]:
break
mat[i][j-1] += 1
mat[i][j] = 0
checkMat[i][j-1] = True
checkMat[i][j] = False
isChanged = True
j -= 1
else:
break
elif d == "r":
for i in range(N):
for j in range(N-2, -1, -1):
if mat[i][j] == 0:
continue
while j < N-1:
if mat[i][j+1] == 0:
mat[i][j+1] = mat[i][j]
mat[i][j] = 0
isChanged = True
j += 1
elif mat[i][j+1] == mat[i][j]:
if checkMat[i][j+1] or checkMat[i][j]:
break
mat[i][j+1] += 1
mat[i][j] = 0
checkMat[i][j+1] = True
checkMat[i][j] = False
isChanged = True
j += 1
else:
break
elif d == "t":
for j in range(N):
for i in range(1, N):
if mat[i][j] == 0:
continue
while i > 0:
if mat[i-1][j] == 0:
mat[i-1][j] = mat[i][j]
mat[i][j] = 0
isChanged = True
i -= 1
elif mat[i-1][j] == mat[i][j]:
if checkMat[i-1][j] or checkMat[i][j]:
break
mat[i-1][j] += 1
mat[i][j] = 0
checkMat[i-1][j] = True
checkMat[i][j] = False
isChanged = True
i -= 1
else:
break
else:
for j in range(N):
for i in range(N-2, -1, -1):
if mat[i][j] == 0:
continue
while i < N -1:
if mat[i+1][j] == 0:
mat[i+1][j] = mat[i][j]
mat[i][j] = 0
isChanged = True
i += 1
elif mat[i+1][j] == mat[i][j]:
if checkMat[i+1][j] or checkMat[i][j]:
break
mat[i+1][j] += 1
mat[i][j] = 0
checkMat[i+1][j] = True
checkMat[i][j] = False
isChanged = True
i += 1
else:
break
return (mat, isChanged)
def checkMaxNum(mat):
curMax = 1
for i in range(N):
for j in range(N):
if curMax < mat[i][j]:
curMax = mat[i][j]
return curMax
N = int(sys.stdin.readline().strip())
converter = { pow(2, i): i for i in range(1, 11)}
converter[0] = 0
originMat = [ [ converter[e] for e in map(int, sys.stdin.readline().strip().split()) ] for _ in range(N)]
maxNum = checkMaxNum(originMat)
queue = deque([(0, originMat)])
directions = [ "l", "r", "t", "b" ]
if N > 1:
while queue:
movingCnt, curMat = queue.pop()
if movingCnt < 5:
for d in directions:
newMat, isChanged = move(curMat, d)
if isChanged:
queue.append((movingCnt+1, newMat))
else:
curMaxNum = checkMaxNum(newMat)
if maxNum < curMaxNum:
maxNum = curMaxNum
else:
# 현재 메트릭스에서 최댓값 찾기?
curMaxNum = checkMaxNum(curMat)
if maxNum < curMaxNum:
maxNum = curMaxNum
answer = pow(2, maxNum)
print(answer)
문제를 풀고 난 후
1. '브루트 포스 알고리즘'이라는 키워드를 알게 되었습니다.
=> 해당 문제의 분류 중에 '브루트 포스 알고리즘'이 있습니다!
2. 제 풀이는 다른 풀이에 비해 속도가 느린 축에 속합니다.
=> 많은 분들의 풀이는 DFS를 사용했고 보드의 블록을 계산하는 과정이 더 단순했습니다!
3. 꼭 보드를 상하좌우로 움직일 필요가 있는가?
=> 많이 풀이 중 가장 짧고 간결한 풀이는 보드를 회전시키며 탐색하는 방법을 이용한 풀이였습니다.(풀이 링크는 아래와 같습니다.)
풀이 링크: hazung.tistory.com/77
*위 링크 속 풀이에서 2차원 리스트를 시계 방향으로 90도 회전시키는 방법은 알아 두는 게 좋을 거 같아 정리를 해보았습니다!
=> 기존 배열을 기준으로 아래와 같이 생각하면 편할 거 같아요ㅎㅎ
기존 배열의 열 -> 회전시킨 배열의 행
기존 배열의 행 -> 회전시킨 배열의 열(단, 끝열부터 채워지도록 배치)
from copy import deepcopy
def rotate(mat):
newMat = deepcopy(mat)
for i in range(3):
for j in range(3):
newMat[j][3-i-1] = mat[i][j]
return newMat
beforeRotation = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
afterRotation = rotate(beforeRotation)
for i in range(3):
print(beforeRotation[i])
print("###################")
for i in range(3):
print(afterRotation[i])
'PS > Python' 카테고리의 다른 글
| [백준] 16236 - 아기 상어(파이썬, Python) (0) | 2021.05.01 |
|---|---|
| [백준] 20056 - 마법사 상어와 파이어볼(파이썬, Python) (0) | 2021.04.29 |
| [백준] 13460 - 구슬 탈출 2 (파이썬, Python) (0) | 2021.04.03 |
| [백준] 13305 - 주유소 (파이썬, Python) (0) | 2021.03.31 |
| [백준] 10816 숫자 카드 2 (파이썬, Python) (0) | 2021.03.31 |