2048 게임 (2048 (Easy))

문제 출처 : 코드트리_2048 게임 (2048 (Easy))
티어 : 골드2
유형 : 시뮬레이션, 백트래킹
출제 : 2016년 하반기 통합 2번
주의사항 : 블럭을 합치는 순서에 주의할 것.

---

바로 전년도와 더불어 4방향의 중력 구현을 수행해야했던 문제입니다. 2개의 사탕을 바로 풀 수 있을 정도의 실력이시라면 크게 어렵지 않았을거라고 생각합니다. 이 기술은 앞으로도 자주 출제되므로, 잘 다룰 수 있도록 기본기를 다집시다.

---

생각의 흐름

격자 판이 최대 다섯 번 까지만 움직이기 때문에 백트래킹 문제라고 생각을 했습니다. 깊이가 더 깊었다면 극한의 가지치기를 요구하는 문제이거나, 혹은 백트래킹 문제가 아니었을 겁니다. 글로벌 변수로 그래프를 사용하는 방법도 있지만 재귀를 통해서 그래프를 전달하는 형식으로 백트래킹을 짜기로 마음먹고 문제를 풀었습니다.

 

스킬

이 문제는 중력에서 더 나아가서, 블럭을 합치는 로직을 어떻게 구현하는지가 중요합니다. 예를 들어 블럭이 아래와 같이 연달아 세 개가 있을 때,

 

우리는 중력을 어떻게 구현해야 할까요?

무턱대고 움직일 수 있는 왼쪽의 블럭부터 움직이게 한다면, 같은 블록을 인식할 때 합쳐지게 동작할 것이므로 그 결과는

 

이렇게 합쳐지게 되겠지요. 그래서 오른쪽으로 움직일 때는 오른쪽 블럭들부터, 왼쪽으로 움직일 때는 왼쪽 블럭들부터 이동시키고 합쳐야 합니다. 그러면 우리가 원하는 결과인

 

이런 움직임을 만들 수 있을거에요!

 

모든 중력의 움직임은 큐의 반복문으로 구현했습니다.

중력을 구현하였으니, 위에서 말했던 주의사항을 기억하며 풀이하겠습니다.

 

아, 참고로 이 문제에는 대표적으로 두 가지 풀이법이 있습니다. 하나는 이번 풀이처럼 모든 방향의 중력을 구현하는 것, 다른 하나는 한 방향만 구현한 후 그래프를 회전시켜서 네 방향 중력을 구현하는 것. 그래프 회전은 다른 문제에서 설명드릴 예정이라, 전자로 풀이했습니다.

 

풀이

from collections import deque

def getInput():
    global N
    N = int(input())
    graph = []
    for _ in range(N):
        graph.extend(list(map(int, input().split())))
    return graph

def right(temp):
    # 오른쪽 중력을 구현한 함수
    for i in range(N):
        q = deque([])
        for j in range(N):
            if temp[N*(i+1)-j-1] == 0: continue
            q.append(temp[N*(i+1)-j-1])
        ttemp = deque([])
        while q:
            ttemp.append(q.popleft())
            if q and q[0] == ttemp[-1]:
                ttemp[-1] *= 2
                q.popleft()
        ttemp += [0]*(N-len(ttemp))
        for j in range(N):
            temp[N*(i+1)-j-1] = ttemp[j]
    return temp

def left(temp):
    # 왼쪽 중력을 구현한 함수
    for i in range(N):
        q = deque([])
        for j in range(N):
            if temp[N*i+j] == 0: continue
            q.append(temp[N*i+j])
        ttemp = deque([])
        while q:
            ttemp.append(q.popleft())
            if q and q[0] == ttemp[-1]:
                ttemp[-1] *= 2
                q.popleft()
        ttemp += [0]*(N-len(ttemp))
        for j in range(N):
            temp[N*i+j] = ttemp[j]
    return temp

def up(temp):
    # 위쪽 중력을 구현한 함수
    for i in range(N):
        q = deque([])
        for j in range(N):
            if temp[N*j+i] == 0: continue
            q.append(temp[N*j+i])
        ttemp = deque([])
        while q:
            ttemp.append(q.popleft())
            if q and q[0] == ttemp[-1]:
                ttemp[-1] *= 2
                q.popleft()
        ttemp += [0]*(N-len(ttemp))
        for j in range(N):
            temp[N*j+i] = ttemp[j]
    return temp

def down(temp):
    # 아래쪽 중력을 구현한 함수
    for i in range(N):
        q = deque([])
        for j in range(N):
            if temp[-N*(j+1)+i] == 0: continue
            q.append(temp[-N*(j+1)+i])
        ttemp = deque([])
        while q:
            ttemp.append(q.popleft())
            if q and q[0] == ttemp[-1]:
                ttemp[-1] *= 2
                q.popleft()
        ttemp += [0]*(N-len(ttemp))
        for j in range(N):
            temp[-N*(j+1)+i] = ttemp[j]
    return temp

def dfs(level, temp):
    # 백트래킹 함수. temp에는 그래프가 들어간다.
    global maxx
    if max(temp)<=maxx//(2**(5-level+1)):
        return
    if level == 5:
        maxx = max(maxx, max(temp))
        return
    dfs(level+1, up(temp[:]))
    dfs(level+1, down(temp[:]))
    dfs(level+1, right(temp[:]))
    dfs(level+1, left(temp[:]))

# ===== 실제 실행하는 부분 =====

def main():
    global maxx
    graph = getInput()

    maxx = 0
    dfs(0, graph)
    print(maxx)

main()