둔필승총

문제 설명

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

문제 자체는 2048 게임을 해보았다면 알 수 있는 문제이다. 물론 게임과는 달리 블록이 추가되지는 않는다. 

처음에 생각한 방법은 브루트포스로 모든 가지수를 해보는 것이다. 최대 5번 이동한다고 하였으므로 사실 모든 가지수를 구하더라도 

4가지 방향에 5번이면 4*4*4*4*4 = 1024 이므로 10의 세제곱 정도면 나머지 연산에서 10000번의 미만의 연산이면 시간 부족 문제는 없을거라 판단하였다. 

물론 왼쪽, 오른쪽, 위, 아래 이동하는 것에서 생각하거나 헷갈려서 오래 걸렸던 것 같다. 그리고 살펴볼 개념이 조금 더 있는 것 같다. 

문제 해설

2번 먼저 생각하면 왼쪽과 오른쪽은 당연히 다른데, 구현하기가 힘들어서 잠깐 생각해보았다.. 

왼쪽 오른쪽과 왼쪽 왼쪽의 결과는 최대값만 구하면 된다고 생각하여 동일한 결과가 나오지 않을까? 라고 생각했는데 

중간에 위로 올라가는 간단한 예시만 들어도 반례를 찾을 수 있다. 

224

022

204

1번과 3번은 같은 맥락이다.

나는 product를 사용하여 중복 순열을 통해서 모든 가지수를 구하였지만, 이를 백트래킹과 DFS를 이용하여 연산의 수를 줄일 수 있다.

def dfs(board, cnt):
    global ans
    if cnt == 5:
        for i in range(n):
            for j in range(n):
                ans = max(ans, board[i][j])
        return

    for i in range(4):
        tmp_board = move(deepcopy(board), i)
        dfs(tmp_board, cnt + 1)

위와 같은 코드를 사용하면 백트래킹과 DFS를 둘 다 적용할 수 있는 코드이다. https://hongcoding.tistory.com/126

사실 4번째 이슈에서 제일 해결못했었는데 python에 대한 문법이였다.

python은 List가 1차원일 경우에는 list.copy()로 복사를 할 수 있지만, 2차원이 넘어갈 경우 오류가 생긴다.

무조건 같은 배열을 깊은 복사하기 위해서는 from copy import deepcopy를 한 뒤 deepcopy를 해서 복사를 하도록 하자. 

코드

from itertools import product
from copy import deepcopy

n = int(input())
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))


def move_left(graph):
    new_graph = graph.copy()
    for i in range(n):
        start_index = 0
        next_index = start_index + 1
        while next_index < n:
            if new_graph[i][start_index] == new_graph[i][next_index]:
                new_graph[i][start_index] = new_graph[i][start_index] + new_graph[i][next_index]
                new_graph[i][next_index] = 0
                start_index = next_index + 1
                next_index = start_index + 1
                if start_index > n or next_index > n:
                    break
            else:
                if new_graph[i][next_index] == 0:
                    next_index += 1
                    if next_index > n:
                        break
                else:
                    start_index = next_index
                    next_index = start_index + 1
                    if start_index > n or next_index > n:
                        break
        temp = new_graph[i]
        zero = []
        for j in range(n):
            if temp[j] == 0:
                zero.append(j)
            else:
                if zero:
                    new_graph[i][zero.pop(0)] = new_graph[i][j]
                    new_graph[i][j] = 0
                    zero.append(j)
    return new_graph


def move_right(graph):
    new_graph = graph.copy()
    for i in range(n):
        start_index = n - 1
        next_index = start_index - 1
        while next_index >= 0:
            if new_graph[i][start_index] == new_graph[i][next_index]:
                new_graph[i][start_index] = new_graph[i][start_index] + new_graph[i][next_index]
                new_graph[i][next_index] = 0
                start_index = next_index - 1
                next_index = start_index - 1
                if start_index <= 0 or next_index < 0:
                    break
            else:
                if new_graph[i][next_index] == 0:
                    next_index -= 1
                    if next_index < 0:
                        break
                else:
                    start_index = next_index
                    next_index = start_index - 1
                    if start_index <= 0 or next_index < 0:
                        break
        temp = new_graph[i]
        zero = []
        for j in range(n - 1, -1, -1):
            if temp[j] == 0:
                zero.append(j)
            else:
                if zero:
                    new_graph[i][zero.pop(0)] = new_graph[i][j]
                    new_graph[i][j] = 0
                    zero.append(j)
    return new_graph


def move_up(graph):
    new_graph = graph.copy()
    for i in range(n):
        start_index = 0
        next_index = start_index + 1
        while next_index < n:
            if new_graph[start_index][i] == new_graph[next_index][i]:
                new_graph[start_index][i] = new_graph[start_index][i] + new_graph[next_index][i]
                new_graph[next_index][i] = 0
                start_index = next_index + 1
                next_index = start_index + 1
                if start_index > n or next_index > n:
                    break
            else:
                if new_graph[next_index][i] == 0:
                    next_index += 1
                    if next_index > n:
                        break
                else:
                    start_index = next_index
                    next_index = start_index + 1
                    if start_index > n or next_index > n:
                        break
        zero = []
        for j in range(n):
            if new_graph[j][i] == 0:
                zero.append(j)
            else:
                if zero:
                    new_graph[zero.pop(0)][i] = new_graph[j][i]
                    new_graph[j][i] = 0
                    zero.append(j)
    return new_graph


def move_down(graph):
    new_graph = graph.copy()
    for i in range(n):
        start_index = n - 1
        next_index = start_index - 1
        while next_index >= 0:
            if new_graph[start_index][i] == new_graph[next_index][i]:
                new_graph[start_index][i] = new_graph[start_index][i] + new_graph[next_index][i]
                new_graph[next_index][i] = 0
                start_index = next_index - 1
                next_index = start_index - 1
                if start_index <= 0 or next_index < 0:
                    break
            else:
                if new_graph[next_index][i] == 0:
                    next_index -= 1
                    if next_index < 0:
                        break
                else:
                    start_index = next_index
                    next_index = start_index - 1
                    if start_index <= 0 or next_index < 0:
                        break
        zero = []
        for j in range(n - 1, -1, -1):
            if new_graph[j][i] == 0:
                zero.append(j)
            else:
                if zero:
                    new_graph[zero.pop(0)][i] = new_graph[j][i]
                    new_graph[j][i] = 0
                    zero.append(j)
    return new_graph


ways = product([0, 1, 2, 3], repeat=5)
ans = 0
for way in ways:
    temp = deepcopy(graph)
    for i in way:
        if i == 0:
            temp = move_left(temp)
        elif i == 1:
            temp = move_right(temp)
        elif i == 2:
            temp = move_up(temp)
        elif i == 3:
            temp = move_down(temp)
    for i in range(n):
        for j in range(n):
            ans = max(ans, temp[i][j])
print(ans)