[백준] 12100 파이썬(python) : 2048 (Easy)

12100번 : 2048 (Easy)

 

 

예제2)

4
2 0 2 8
0 0 2 2
0 0 0 0
0 0 0 0
# 16

 

예제3)

4
2 4 16 8
8 4 0 0
16 8 2 0
2 8 2 0
# 32

 

백트래킹 문제이다. 상하좌우 블록을 미는 함수를 구현해주는것이 포인트인데 블록들을 비교하기 위해 특정 위치를 가리키는 포인터를 사용할 수 있다. 블록을 위로 미는 과정을 생각하면 열의 첫번째 행을 포인터로 설정하고 열의 두번째 행부터 현재행으로 설정하여 포인터와의 비교를 해주며 블록을 밀 수 있다.

 

포인터와의 비교를 위해서는 항상 현재 가리키는 블록은 0이 아닌 블록이어야 한다.

포인터와 현재행이 만나수 있는 경우는 3가지가 있는데 다음과 같다.

 

1. 포인터가 가리키는 블록이 0일때
2. 포인터가 가리키는 블록이 현재블록과 같을때
3. 포인터가 가리키는 블록이 현재블록과 다를때

 

블록을 위로 밀때를 예시로 들때 포인터가 가리키는 숫자가 0이라면, 그 자리에 0이 현재블록을 배치시키고 현재위치의 블록을 0으로 바꿔준다.

포인터가 가리키는 블록이 현재블록과 같다면 포인터가 가리키는 블록을 x2해주고 현재블록을 0으로 만든다. 그리고 포인터를 하나 증가시킨다.

포인터가 가리키는 블록이 현재블록과 다를때는 그 다음 위치에 쌓여야 하기 때문에 포인터를 증가시키고 포인터의 위치에 현재블록을 배치시킨다.(포인터가 다음 위치의 블록은 0이다)

 

블록을 위로 미는 과정

블록을 오른쪽으로 미는 과정

블록을 위로 미는 과정

블록을 위로 미는 과정 (3번사용)

 

import sys
from copy import deepcopy
n = int(sys.stdin.readline())
graph = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ]
res = 0

def up(graph):
    for j in range(n):
        p = 0
        for i in range(1, n):
            if graph[i][j]:
                temp = graph[i][j]
                graph[i][j] = 0

                if graph[p][j] == 0:
                    graph[p][j] = temp
                elif graph[p][j] == temp:
                    graph[p][j] *= 2
                    p += 1
                else:
                    p += 1
                    graph[p][j] = temp
    return graph

def down(graph):
    for j in range(n):
        p = n-1
        for i in range(n-2, -1, -1):
            if graph[i][j]:
                tmp = graph[i][j]
                graph[i][j] = 0

                if graph[p][j] == 0: #1
                    graph[p][j] = tmp
                elif graph[p][j] == tmp: #2
                    graph[p][j] *= 2
                    p -= 1
                else: #3
                    p -= 1
                    graph[p][j] = tmp
    return graph

def left(graph):
    for i in range(n):
        p = 0
        for j in range(1, n):
            if graph[i][j]:
                tmp = graph[i][j]
                graph[i][j] = 0

                if graph[i][p] == 0:
                    graph[i][p] = tmp
                elif graph[i][p] == tmp:
                    graph[i][p] *= 2
                    p += 1
                else:
                    p += 1
                    graph[i][p] = tmp
    return graph

def right(graph):
    for i in range(n):
        p = n-1
        for j in range(n-2, -1, -1):
            if graph[i][j]:
                tmp = graph[i][j]
                graph[i][j] = 0

                if graph[i][p] == 0:
                    graph[i][p] = tmp
                elif graph[i][p] == tmp:
                    graph[i][p] *= 2
                    p -= 1
                else:
                    p -= 1
                    graph[i][p] = tmp
    return graph

def backTracking(graph, cnt):
    global res
    if cnt == 5:
        res = max(res, max(map(max, graph)))
        return
    backTracking(up(deepcopy(graph)), cnt+1)
    backTracking(down(deepcopy(graph)), cnt+1)
    backTracking(left(deepcopy(graph)), cnt+1)
    backTracking(right(deepcopy(graph)), cnt+1)

backTracking(graph, 0)
print(res)

 

상하좌우를 표현할때는 동쪽으로 이동후 5번이 지나서 최대 블록을 만든 뒤에는 다시 1번에서 서쪽으로 가서 5번을 지나는 경우를 만들어줘야 하기 때문에 배열에 변형이 있으면 안된다. 그래서 "깊은 복사"를 사용하여 백트래킹을 진행한다.

 

---

포스팅1

포스팅2