[algorithm] 백준 2048 (Easy) #12100
해당 블로그는 개인이 공부하고, 정리한 걸 기록하는 공간입니다.
오타, 오류가 존재할 수 있습니다. 댓글을 달아주시면 수정할 수 있도록 하겠습니다.
코드 보기
import copy
def rotate(m, radis):
N = len(m)
ret = [[0] * N for _ in range(N)]
for r in range(N):
for c in range(N):
if radis == 90:
ret[c][N-1-r] = m[r][c]
elif radis == 180:
ret[N-1-r][N-1-c] = m[r][c]
elif radis == 270:
ret[N-1-c][r] = m[r][c]
return ret
def move(lines): # 무조건 왼쪽으로만 이동시킴.
lines_copy = copy.deepcopy(lines)
for idx, line in enumerate(lines_copy): # 위에서 아래
new_line = []
check = []
while line: # 하나 라인 이동 완료할 때까지
num = line.pop(0)
if not num:
continue
new_line.append(num)
if len(new_line) > 1 and new_line[-1] == new_line[-2]:
new_line.pop()
new_line.append(new_line.pop() * 2)
check += new_line
new_line = []
check += new_line
while len(check) < n:
check.append(0)
lines_copy[idx] = check
return lines_copy
def go(lines, cnt):
if cnt == 5: # 최대 5번
return max([max(line) for line in lines])
cnt += 1
# 회전 후 이동
down = rotate(move(rotate(lines, 90)), 270)
up = rotate(move(rotate(lines, 270)), 90)
left = move(lines)
right = rotate(move(rotate(lines, 180)), 180)
return max(go(left, cnt), go(right, cnt), go(up, cnt), go(down, cnt))
n = int(input())
lines = [list(map(int, input().split())) for _ in range(n)]
print(go(lines, 0))
2048 (Easy)
문제 설명
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 27845 | 7035 | 4098 | 23.315% |
2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.
이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)
<그림 1>
<그림 2>
<그림 3>
<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.
<그림 4>
<그림 5>
<그림 6>
<그림 7>
<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.
<그림 8>
<그림 9>
<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.
<그림 10>
<그림 11>
<그림 12>
<그림 13>
<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다.
<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.
<그림 14>
<그림 15>
마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.
이 문제에서 다루는 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
알고리즘 분류
설명 & 구현 방법
알고리즘 분류에도 적혀있듯이 해당 문제는 브루트 포스를 통해 해결하면 된다. 가장 depth 깊어도 5 이하로는 내려가 않는 것이 조건이므로, 상황마다 왼쪽, 오른쪽, 위, 아래로 해보면 된다.
나같은 경우 왼쪽으로 이동시키는 함수 하나만 만들었다.
그리고 보드를 90도씩 회전 시키면서 해당 함수를 적용시켰다.
하나의 보드마다 90도씩 회전시켜서 모든 보드(총 4개)에 함수를 적용시켰다.
이렇게 진행되다가 깊이가 5가 되면 해당 보드에서 가장 큰 값을 반환했다.
반환된 값들 중 가장 큰 값을 반환해주면 된다.
모든 경우를 다 탐색하면 된다는 점에서 엄청 어려운 문제는 아니였다.
댓글남기기