BOJ 12100번 : 2048 (easy) - Python

Q. 문제

https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

 

 

 

 

A. 풀이

[python]

from collections import deque

N = int(input())
mp = [[*map(int, input().split())] for _ in range(N)]


def bfs():
    dq = deque()
    dq.append(mp)
    ans = 0
    for c in range(6):
        for qs in range(len(dq)):
            v = dq.popleft()
            
            for i in range(N):
                for j in range(N):
                    ans = max(ans, v[i][j])

            # up
            vv = [[0] * N for _ in range(N)]
            for j in range(N):
                q = deque()
                for i in range(N):
                    if v[i][j] != 0:
                        if len(q) > 0 and q[len(q) - 1] == v[i][j]:
                            q.pop()
                            q.append(v[i][j] * -2)
                        else:
                            q.append(v[i][j])
                for i in range(N):
                    if len(q) > 0:
                        vv[i][j] = abs(q.popleft())
                    else:
                        vv[i][j] = 0
            dq.append(vv)

            # down
            vv = [[0] * N for _ in range(N)]
            for j in range(N):
                q = deque()
                for i in range(N - 1, -1, -1):
                    if v[i][j] != 0:
                        if len(q) > 0 and q[len(q) - 1] == v[i][j]:
                            q.pop()
                            q.append(v[i][j] * -2)
                        else:
                            q.append(v[i][j])
                for i in range(N - 1, -1, -1):
                    if len(q) > 0:
                        vv[i][j] = abs(q.popleft())
                    else:
                        vv[i][j] = 0
            dq.append(vv)

            # right
            vv = [[0] * N for _ in range(N)]
            for i in range(N):
                q = deque()
                for j in range(N-1, -1, -1):
                    if v[i][j] != 0:
                        if len(q) > 0 and q[len(q) - 1] == v[i][j]:
                            q.pop()
                            q.append(v[i][j] * -2)
                        else:
                            q.append(v[i][j])
                for j in range(N-1, -1, -1):
                    if len(q) > 0:
                        vv[i][j] = abs(q.popleft())
                    else:
                        vv[i][j] = 0
            dq.append(vv)

            # left
            vv = [[0] * N for _ in range(N)]
            for i in range(N):
                q = deque()
                for j in range(N):
                    if v[i][j] != 0:
                        if len(q) > 0 and q[len(q) - 1] == v[i][j]:
                            q.pop()
                            q.append(v[i][j] * -2)
                        else:
                            q.append(v[i][j])
                for j in range(N):
                    if len(q) > 0:
                        vv[i][j] = abs(q.popleft())
                    else:
                        vv[i][j] = 0
            dq.append(vv)

    return ans

print(bfs())

 

dfs/bfs + 시뮬레이션

 

1. 위, 아래, 왼쪽, 오른쪽 - 4방향으로 맵 밀기

2. 5번 안에 최고 숫자

3. 한 타임에, 한 번 합쳐진 수는 또 합쳐질 수 없음

 

 

저는 큐를 만들어서 이동할 수 있는 모든 경우를 큐에 저장했습니다.

그래서 큐에서 맵을 하나씩 꺼내서 4방향으로 이동한 결과를 다시 큐로 push 했습니다. (python 은 append)

for 문의 start index와 end index에 따라 맵을 미는 방향이 바뀌는데, 

자꾸 left를 미는 게 안 되는걸 찾다보니까 맵 초기화를 매 방향마다 해주는걸 놓쳐서 고생했습니다 ㅠㅠ

 

.