[Python - Backtracking, DFS, Queue] 12100 2048(Easy)

📌 문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

 

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

 

 

<그림 1>

<그림2>

<그림 3>

<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.

<그림 4>

<그림 5>

<그림 6>

<그림 7>

<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.

<그림 8>

<그림 9>

<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.

<그림 10>

<그림 11>

<그림 12>

<그림 13>

<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다. 

 

<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.

<그림 14>

<그림 15>

마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.

 

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

📌 입력

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

📌 출력

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

📌 문제 풀이

👨‍🏫 접근

상하좌우 이동이 가능하며, 각 이동마다 값이 제각각 달라지고 이 값이 다음 진행에 큰 영향을 미친다. 그리고 종료 조건도 있으며, 기반 정보도 주어지기에 백트래킹으로 문제를 풀기에 알맞았다.

 

여기서 중요한 것은, 어떻게 상하좌우 이동을 구현할 것이냐는 것이다.

 

나의 경우 for문으로 그래프를 돌면서 값을 갱신하는 방향으로 문제를 풀어갔다. 여기서 중요한 것은 어떻게 순회하냐는 것이다. 이때는 이동 방향이 중요한 영향을 끼친다. 이동방향과 반대방향으로 순회하되, 값을 합치는 것은 이동방향과 같은 방향으로 합쳐야 하기 때문이다.

여기서 왼쪽으로 이동한다고 하면, 첫 번째 행에서는 2와 2를 더해 4를 만든다.

이런 식으로 이동을 구현하도록 한다. 그런데 주의할 점이 있다.

바로 이미 처리된 값을 다시 처리하는 경우이다.

 

위에서는 원래 이동이라면 첫 행에서 4 4 0 0을 가져야 하는데, 그냥 모두 이동하면서 모두 더하면 8 0 0 0이라는 값을 가지게 된다. 이는 문제의 요구의 맞지 않는다. 그래서 처리 테이블을 구현해줬다.

 

그래서, 왼쪽의 이동을 예로 들면 아래와 같다.

def go_left(graph):
    graph = copy.deepcopy(graph)
    processed = [[False] * n for _ in range(n)]

    for x in range(n):
        for y in range(1, n):
            if graph[x][y] != 0:
                while y > 0 and graph[x][y - 1] == 0:
                    graph[x][y], graph[x][y - 1] = graph[x][y - 1], graph[x][y]
                    y -= 1
                if y > 0 and graph[x][y - 1] == graph[x][y]:
                    if not processed[x][y - 1]:
                        processed[x][y - 1] = True
                        graph[x][y - 1] += graph[x][y]
                        graph[x][y] = 0

    return graph

여기서 보면 copy 모듈을 사용하고 있다. 왜 copy 모듈로 깊은 복사를 해야 할까?

 

그 이유는 반복문에서 원본 그래프의 값을 바꾸기 때문에 백트래킹에서 원본 그래프를 보존하지 못하기 때문이다. 그래서 copy 모듈의 deepcopy 메서드로 복사해준다.

 

문제를 푼 다음에 구글링하면서 다른 사람들의 풀이를 봤는데, 큐를 사용해서 풀 수 있었다.

기존의 for문으로 순환하는 것은 아래와 같은 과정을 거친다.

1. 원본 그래프를 복사한다.
2. 처리 테이블을 만들어 재처리를 방지한다.
3. 1번(혹은 n - 1번 인덱스)부터 순회하며 0을 만날 때까지 이동방향의 반대로 탐색한다.
4. 만약 탐색하여 값이 같다면 테이블에 방문처리한 후에 더하고 같지 않다면 멈춘다.

하지만 큐를 사용하면 아래와 같이 풀이할 수 있다.

1. 원본 그래프를 복사한다.
2. 그래프를 순회하여 값이 있는 곳의 좌표값을 받아 큐에 넣는다. 그 좌표의 값은 0으로 갱신한다.
3. q가 빌 때까지 반복하며, 0번 인덱스부터 끝까지 순회한다.
4. 일단, 큐에서 값을 추출하여 현 인덱스 값이 0이거나 같지 않다면 그대로 값을 넣어주고, 같은 값이라면 좌표값을 2배로 곱하여 더해준 다음 인덱스를 1 늘린다(0이 아니고 같지 않은 경우에도 인덱스를 1 늘린다).

이렇게 하면 4 0 0 0 0 0 0 2 같이 멀리 떨어져 있어도, 큐로 idx에 바로 값을 넣어서 4 2 0 0 0 0 0 0으로 쉽게 바꿀 수 있다. 대박

👨‍🏫 문제 풀이

📄 전체 코드

import sys
import copy
input = sys.stdin.readline

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


def go_up(graph):
    graph = copy.deepcopy(graph)
    processed = [[False] * n for _ in range(n)]

    for y in range(n):
        for x in range(1, n):
            if graph[x][y] != 0:
                while x > 0 and graph[x - 1][y] == 0:
                    graph[x][y], graph[x - 1][y] = graph[x - 1][y], graph[x][y]
                    x -= 1
                if x > 0 and graph[x - 1][y] == graph[x][y]:  # x == 0이면 마지막 인덱스와 비교함
                    if not processed[x - 1][y]:  # 만약 한 번도 안 합쳤었다면
                        processed[x - 1][y] = True
                        graph[x - 1][y] += graph[x][y]
                        graph[x][y] = 0

    return graph


def go_left(graph):
    graph = copy.deepcopy(graph)
    processed = [[False] * n for _ in range(n)]

    for x in range(n):
        for y in range(1, n):
            if graph[x][y] != 0:
                while y > 0 and graph[x][y - 1] == 0:
                    graph[x][y], graph[x][y - 1] = graph[x][y - 1], graph[x][y]
                    y -= 1
                if y > 0 and graph[x][y - 1] == graph[x][y]:
                    if not processed[x][y - 1]:
                        processed[x][y - 1] = True
                        graph[x][y - 1] += graph[x][y]
                        graph[x][y] = 0

    return graph


def go_right(graph):
    graph = copy.deepcopy(graph)
    processed = [[False] * n for _ in range(n)]

    for x in range(n):
        for y in range(n - 2, -1, -1):
            if graph[x][y] != 0:
                while y < n - 1 and graph[x][y + 1] == 0:
                    graph[x][y + 1], graph[x][y] = graph[x][y], graph[x][y + 1]
                    y += 1
                if y < n - 1 and graph[x][y + 1] == graph[x][y]:
                    if not processed[x][y + 1]:
                        processed[x][y + 1] = True
                        graph[x][y + 1] += graph[x][y]
                        graph[x][y] = 0

    return graph


def go_down(graph):
    graph = copy.deepcopy(graph)
    processed = [[False] * n for _ in range(n)]
    for y in range(n):
        for x in range(n - 2, -1, -1):
            if graph[x][y] != 0:
                while x < n - 1 and graph[x + 1][y] == 0:
                    graph[x + 1][y], graph[x][y] = graph[x][y], graph[x + 1][y]
                    x += 1
                if x < n - 1 and graph[x + 1][y] == graph[x][y]:
                    if not processed[x + 1][y]:
                        processed[x + 1][y] = True
                        graph[x + 1][y] += graph[x][y]
                        graph[x][y] = 0

    return graph


ans = -1


def solve(cnt, graph):
    global ans
    if cnt == 5:
        ans = max(ans, max(map(max, graph)))
        return

    solve(cnt + 1, go_left(graph))
    solve(cnt + 1, go_right(graph))
    solve(cnt + 1, go_up(graph))
    solve(cnt + 1, go_down(graph))


solve(0, board)
print(ans)

📄 준비

import sys
import copy
input = sys.stdin.readline

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


def go_up(graph):
    graph = copy.deepcopy(graph)
    processed = [[False] * n for _ in range(n)]

    for y in range(n):
        for x in range(1, n):
            if graph[x][y] != 0:
                while x > 0 and graph[x - 1][y] == 0:
                    graph[x][y], graph[x - 1][y] = graph[x - 1][y], graph[x][y]
                    x -= 1
                if x > 0 and graph[x - 1][y] == graph[x][y]:  # x == 0이면 마지막 인덱스와 비교함
                    if not processed[x - 1][y]:  # 만약 한 번도 안 합쳤었다면
                        processed[x - 1][y] = True
                        graph[x - 1][y] += graph[x][y]
                        graph[x][y] = 0

    return graph


def go_left(graph):
    graph = copy.deepcopy(graph)
    processed = [[False] * n for _ in range(n)]

    for x in range(n):
        for y in range(1, n):
            if graph[x][y] != 0:
                while y > 0 and graph[x][y - 1] == 0:
                    graph[x][y], graph[x][y - 1] = graph[x][y - 1], graph[x][y]
                    y -= 1
                if y > 0 and graph[x][y - 1] == graph[x][y]:
                    if not processed[x][y - 1]:
                        processed[x][y - 1] = True
                        graph[x][y - 1] += graph[x][y]
                        graph[x][y] = 0

    return graph


def go_right(graph):
    graph = copy.deepcopy(graph)
    processed = [[False] * n for _ in range(n)]

    for x in range(n):
        for y in range(n - 2, -1, -1):
            if graph[x][y] != 0:
                while y < n - 1 and graph[x][y + 1] == 0:
                    graph[x][y + 1], graph[x][y] = graph[x][y], graph[x][y + 1]
                    y += 1
                if y < n - 1 and graph[x][y + 1] == graph[x][y]:
                    if not processed[x][y + 1]:
                        processed[x][y + 1] = True
                        graph[x][y + 1] += graph[x][y]
                        graph[x][y] = 0

    return graph


def go_down(graph):
    graph = copy.deepcopy(graph)
    processed = [[False] * n for _ in range(n)]
    for y in range(n):
        for x in range(n - 2, -1, -1):
            if graph[x][y] != 0:
                while x < n - 1 and graph[x + 1][y] == 0:
                    graph[x + 1][y], graph[x][y] = graph[x][y], graph[x + 1][y]
                    x += 1
                if x < n - 1 and graph[x + 1][y] == graph[x][y]:
                    if not processed[x + 1][y]:
                        processed[x + 1][y] = True
                        graph[x + 1][y] += graph[x][y]
                        graph[x][y] = 0

    return graph


ans = -1

빡구현을 해버렸다. 조금 더 쉬운 방법이 있었거늘,,,

 

각 이동은 모두 다르게 처리해줘야 한다.

📄 풀이

def solve(cnt, graph):
    global ans
    if cnt == 5:
        ans = max(ans, max(map(max, graph)))
        return

    solve(cnt + 1, go_left(graph))
    solve(cnt + 1, go_right(graph))
    solve(cnt + 1, go_up(graph))
    solve(cnt + 1, go_down(graph))


solve(0, board)
print(ans)

 

📌 총평

이런 문제를 많이 풀어봐야겠다. 구현력이 조금 부족했던 시간이었다. 일단 그래프를 복사하지 않고 문제를 계속 풀어서 이 부분이 좀 아쉬웠던 부분이었다.