[Python] 12100번. 2048 (Easy)

문제 링크

성능 요약

메모리: 32412 KB, 시간: 120 ms

분류

구현, 브루트포스 알고리즘, 시뮬레이션, 백트래킹

 

# 1.입력/변수 정의
N=int(input())
board=[list(map(int,input().split())) for _ in range(N)]
ans=0 

# 2.알고리즘
"""
DFS를 이용한다.
1. 한쪽 방향으로 보드를 민다(왼쪽 방향으로)
2. 민 보드를 계산한다
3. 계산된 보드는 다음 DFS로 넘긴다
4. 보드를 회전한다
-> 4방향으로 계속 돌려야하므로 총 모든 경우의 수는 4^5=1024
"""

def rotate(b):
    return list(zip(*b[::-1]))

def move_left(b):
    new_board=[]
    for row in b:
        tmp=[x for x in row if x!=0]
        new_row=[]
        i=0
        while i<len(tmp):
            if i+1<len(tmp) and tmp[i]==tmp[i+1]:
                new_row.append(tmp[i]*2)
                i+=2
            else:
                new_row.append(tmp[i])
                i+=1
        new_row+=[0]*(N-len(new_row))
        new_board.append(new_row)
    return new_board

def dfs(c,b):
    global ans

    # 만약 5번 이동시켰다면
    if c==5:
        for r in b:
            ans=max(ans,max(r))
        return

    for _ in range(4):
        next_board=move_left(b)
        dfs(c+1, next_board)
        b=rotate(b)

# 3.출력
# 4방향으로 돌릴 수 있다
dfs(0,board)
print(ans)

 

이번 문제는 

2026.01.06 - [coding test/Baekjoon] - [Python] 23796. 2,147,483,648 게임

[Python] 23796번. 2,147,483,648 게임

백준의 23796번 문제와 유사했다고 생각한다.

하지만 최대 5번을 이동시킨다고 생각하면 총 4^5=1024번의 경우를 생각해야하는데 다행히 이번 문제에서는 시간 초과가 나지는 않았다.

이 문제의 경우 모든 경우를 생각할 수 밖에 없는 문제이기도 하다.

 

한 보드에서 위/아래/왼쪽/오른쪽으로 밀 것인지 총 4가지의 경우의 수가 나온다.

처음에는 단순히 하드코딩을 생각했는데 질문 게시판을 보니까 보드를 회전해서 풀길래 굉장하다고 생각했고 `rotate`라는 함수를 정의해 for문으로 하니 엄청 간단해졌다!

보드는 회전하는 코드는 엄청 간단했는데 `zip`을 사용하였다.

 

파이썬 `zip()`함수는 여러 iterable(리스트, 튜플 등)의 동일한 인덱스에 있는 요소들을 순서대로 묶어 튜플로 반환한다.

그렇기 때문에 `list(zip(*b[::-1]))`은 다음과 같이 나오게 된다.

 

예시를 들면

예제

b=[
    [1,2,3],
    [4,5,6],
    [7,8,9]
]

1. `b[::-1]` ▶ 행 순서 뒤집기

[
    [7,8,9],
    [4,5,6],
    [1,2,3]
]

2. `*b[::-1]` ▶ 언패킹(unpacking) 

`zip(*b[::-1])`은 결국 `zip([7,8,9],[4,5,6],[1,2,3])`이 된다.

`zip(*b[::-1])` = `zip([7,8,9],[4,5,6],[1,2,3])`

3. `zip(*b[::-1])` ▶ 열→행 변환 전치

`zip(*b[::-1])`은 같은 인덱스에 있는 값을 묶는다.

그렇기 때문에 다음과 같은 결과가 된다.

(7, 4, 1)
(8, 5, 2)
(9, 6, 3)

4. `list(...)` ▶ 최종 리스트 변환

zip의 결과는 리스트가 아니다.

그렇기 때문에 나온 결과를 `list`로 감싸서 `list`로 만든다.

[
	(7, 4, 1),
	(8, 5, 2),
	(9, 6, 3),
]