[백준 12100] 2048(Easy)

1. 문제

www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

2. 접근 방법

1. 숫자 블록을 움직이는 단계: 상/하/좌/우

1-1. 방향에 따라 해당 열or 행을 큐에 넣는다.

1-2. 빈 공간은 큐에 담지 않는다.

1-3. 블록을 넣었다면 블록에 있던 자리는 빈 공간으로 만든다.

2. 블록을 합치는 단계

2-1. 큐에서 블록을 꺼내고 이를 순서대로 보드와 비교하면서 진행

2-2. 만약 현재 좌표보드가 빈공간이라면, 큐에 꺼낸 숫자를 그대로 보드에 넣는다.

2-3. 만약 현재 좌표보드가 빈공간이 아니라면, 큐에서 꺼낸 블록과 값이 일치하는지 비교한다.

2-4. 현재 좌표보드가 빈공간이 아니고, 큐에서 꺼낸 블록과 값이 일치한다면 현재 좌표보드의 숫자*2해준다. 그리고 좌표보드를 한 칸 이동한다.

2-5. 현재 좌표보드가 빈공간이 아니고, 큐에서 꺼낸 블록과 값이 다르다면 좌표보드를 한 칸 이동한 후 큐에서 꺼낸 블록을 보드에 넣는다.

3. 코드

python

from collections import deque

def get(x, y):
    # 방향에 따라 한 줄씩 queue에 숫자 담기 (0 제외)
    if board[y][x]:
        q.append(board[y][x])
        board[y][x] = 0

def merge(x, y, dx, dy):
    # 한 줄당 queue
    while q:
        # queue에서 하나씩 뽑아서
        num = q.popleft()
        # 만약 현재 위치에 처음 온거라면
        if not board[y][x]:
            # 숫자 담아주기
            board[y][x] = num
        # 만약 현재 위치에 있는 숫자와 지금 뽑은 숫자가 같다면,
        elif board[y][x] == num:
            # 숫자 2배하고
            board[y][x] = num*2
            # 자리 이동
            x, y = x+dx, y+dy
        # 현재 위치에 있는 숫자와 지금 뽑은 숫자가 같지 않다면,
        else:
            # 위치 이동
            x, y = x+dx, y+dy
            # 후에 숫자 담기
            board[y][x] = num

def move(k):
    global N
    # 왼쪽으로 밀었을 때
    if k == 0:
        for y in range(N):
            for x in range(N):
                get(x, y)
            merge(0, y, 1, 0)
    # 오른쪽으로 밀었을 때
    elif k == 1:
        for y in range(N):
            for x in range(N-1, -1, -1):
                get(x, y)
            merge(N-1, y, -1, 0)
    # 위로 밀었을 때
    elif k == 2:
        for x in range(N):
            for y in range(N):
                get(x, y)
            merge(x, 0, 0, 1)
    # 아래로 밀었을 때
    else:
        for x in range(N):
            for y in range(N-1, -1, -1):
                get(x, y)
            merge(x, N-1, 0, -1)

def solve(cnt):
    global board, ans, N
    # 5번째 이동이라면
    if cnt == 5:
        # 기존의 최댓 값과 현재 board의 최댓 값 중 더 큰 것으로 갱신
        for i in range(N):
            ans = max(ans, max(board[i]))
        return
    # board 복제
    temp = [x[:] for x in board]
    # k는 상, 하, 좌, 우
    for k in range(4):
        move(k)
        solve(cnt+1)
        # board 초기화(방향을 바꿀 때마다 원래의 보드를 사용해야함)
        board = [x[:] for x in temp]

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
ans = 0
q = deque()

solve(0)
print(ans)

4. 마치며

코드 참고는 여기서 했습니다.

rebas.kr/763

BOJ 12100 · 2048 (Easy)

크게 숫자 블록을 움직이는 것과 블록을 합치는 것으로 나누는 것 까지는 생각을 했는데,

숫자 블록을 움직일 때 큐에 넣을 생각은 하지 못했네요 ^-^~!

후우

 

그리고 좌표 보드의 방향을 바꿔서 움직일 때마다 board를 초기화해주는 것을 생각하지 못했슴다.

ㅠㅠ

 

말랑말랑한 머리가 되기를 !!!!!!!!!!!!!!!!!!!!!!!!