[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 12100번 _ 2048(EASY)

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

12100번: 2048 (Easy)

[문제]

위 링크 참조

 

[입력]

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

[출력]

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

 

[아이디어]

1) transpose와 reverse를 구현하면, 왼쪽으로의 합만을 이용해 모든 방향의 합을 계산할 수 있다.

2) n번 이동 시에는 4**n개의 가능한 이동이 존재하며, 이 모든 경우를 체크해야한다. (product 이용해 모든 케이스 구현 가능)

 

# sum_ 부분 틀림
from itertools import product
n=int(input())
b = [list(map(int,input().split())) for _ in range(n)]
p = product("LRUD","LRUD","LRUD","LRUD","LRUD")

def transpose(x):
    return map(list, zip(*x))

def reverse(x):
    return map(lambda x: list(reversed(x)), x)

def sum_(x):
    global n
    s = []
    check = -1
    for i,num in enumerate(x):
        if num!=0:
            if not s:
                s.append(num)
            else:
                if s[-1]==num and check+1!=i:
                    s[-1] = num*2
                    check = i
                else:
                    s.append(num)
    s += (n-len(s))*[0]
    return s

ans = 2
for x in p:
    board = b.copy()
    for move in x:
        if move=="L":
            board = map(sum_, board)
        elif move=="R":
            board = reverse(map(sum_, reverse(board)))
        elif move=="U":
            board = transpose(map(sum_, transpose(board)))
        else:
            board = transpose(reverse(map(sum_, reverse(transpose(board)))))
    ans = max(max(map(max,board)),ans)
print(ans)

L를 제외한 연산을 하는 경우 반복해서 행렬을 변환해야하는 것이 조금 비효율적이긴 하지만, 최대 이동 횟수가 5라는 점에서 충분히 가능하다고 생각했다. 다만 왼쪽 합인 sum_의 구현에서 아래와 같은 오류가 발생하는 경우를 놓쳤다.

당연히 맨 처음에는 합쳐질 때마다 일종의 block(정답 코드에서는 0)을 생성하고, 나중에 다시 이것을 삭제하는 방법을 떠올리긴 했으나 반복문을 2번 통과시켜야하는 것을 피하고자 연속된 index에서의 연속적인 숫자 결합이 일어나지 않도록 코드를 짰는데, 위의 반례처럼 연속되지 않는 경우라하더라도 합쳐지면 안되는 케이스를 놓치고 있었다.

from itertools import product
n=int(input())
b = [list(map(int,input().split())) for _ in range(n)]
p = product("LRUD","LRUD","LRUD","LRUD","LRUD")

def transpose(x):
    return map(list, zip(*x))

def reverse(x):
    return map(lambda x: list(reversed(x)), x)

def sum_(x):
    global n
    s = [i for i in x if i!=0]
    for i in range(len(s)-1):
        if s[i]==s[i+1]:
            s[i], s[i+1] = 2*s[i], 0
    s = [i for i in s if i!=0]
    return s + (n-len(s))*[0]

ans = 0
for x in p:
    board = b.copy()
    for move in x:
        if move=="L":
            board = map(sum_, board)
        elif move=="R":
            board = reverse(map(sum_, reverse(board)))
        elif move=="U":
            board = transpose(map(sum_, transpose(board)))
        else:
            board = transpose(reverse(map(sum_, reverse(transpose(board)))))
    ans = max(max(map(max,board)),ans)
print(ans)

sum_ 부분을 수정해 통과했다. 행렬을 90도씩 회전해가며 왼쪽 합만으로 게임을 진행하는 코드도 있었는데, 속도 면에서는 크게 차이나지 않는다.