[solved.ac 골드2] 12100_2048 (Easy) (파이썬, 구현, 행렬, BFS)

밑의 사진을 클릭하면 문제 링크로 이동합니다

제한 사항

문제

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번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

 

예제

---

나의 풀이

2048 게임은 학창 시절에 재밌게 했었던 추억의 게임이다. (거의 10년 전...)

 

이 문제의 알고리즘 분류가 백트래킹으로 되어 있는데 나는 이걸 안 보고 풀어서 BFS로 풀이했다.

사실 BFS보다도 빡구현으로 풀었다고 하는 것이 더 맞을 것 같다.

우선 이 2048 게임은 상, 하, 좌, 우로 이동할 수 있는데 게임판이 주어졌을 때 이동 후에 어떻게 변할 지 구현해야 한다.

나는 처음에는 상, 하, 좌, 우 4개의 경우를 모두 만들어서 문제 풀이에 성공했는데 좀 더 모듈화를 하고 묶어서 풀어보고 싶어서 다시 풀게 되었다.

다시 풀었을 때는 왼쪽으로 움직이는 경우 하나만을 만들었고, 나머지 상, 하, 우로 움직이는 동작은 왼쪽으로 움직이는 경우를 가지고 조작했다.

예를 들어 위로 움직이는 경우는 게임 판을 왼쪽(270도)으로 회전시킨 후 왼쪽으로 움직이고, 다시 오른쪽(90도)으로 회전하는 방식이다.

 

그리고 bfs 함수 내에서 일반적으로 4개 방향을 반복문으로 처리하기 때문에 이번 풀이에서도 다음과 같이 나타했다.

def move(board, i):
    if i == 0:
        return move_up(board)
    elif i == 1:
        return move_down(board)
    elif i == 2:
        return move_left(board)
    elif i == 3:
        return move_right(board)

게임판과 방향(0~4)이 주어지면 분기해서 동작한다.

왼쪽으로 움직이는 함수가 잘 구현됐다고 했을 때 나머지 동작은 다음과 같다. (참고로 왼쪽으로 움직이는 함수는 왼쪽으로 움직인 후의 게임 판과 게임 판의 최댓값을 같이 return한다)

def move_right(board):
    new_board, max_num = move_left(flip(board))
    return flip(new_board), max_num

오른쪽으로 움직이는 것은

1. 게임 판을 좌, 우로 뒤집는다
2. 왼쪽으로 이동한다
3. 이동한 결과를 다시 좌, 우로 뒤집는다

 

def move_down(board):
    new_board, max_num = move_left(turn_right(board))
    return turn_left(new_board), max_num

아래로 움직이는 것은

1. 시계 방향으로 90도 돌린다
2. 왼쪽으로 이동한다
3. 반시계 방향으로 90도 돌린다

 

def move_up(board):
    new_board, max_num = move_left(turn_left(board))
    return turn_right(new_board), max_num

위로 움직이는 것은

1. 반시계 방향으로 90도 돌린다
2. 왼쪽으로 이동한다
3. 시계 방향으로 90도 돌린다

 

위 함수에서 사용된 flip(좌, 우로 뒤집는 함수), turn_right(시계 방향으로 90도 회전하는 함수), turn_left(반시계 방향으로 90도 회전하는 함수)는 다음과 같다.

def flip(board):
    return tuple([tuple(row[::-1]) for row in board])


def turn_right(board):
    return tuple(map(tuple, zip(*board[::-1])))


def turn_left(board):
    ret = [[0] * n for _ in range(n)]
    for x in range(n):
        for y in range(n):
            ret[n - 1 - y][x] = board[x][y]
    return tuple(tuple(row) for row in ret)

주목할 점은 리스트가 아닌 튜플로 처리했다는 건데, 그 이유는 BFS를 할 때 SET으로 중복 처리를 하는데 SET은 Immutable 타입인 튜플로 넣어줘야 하기 때문이다. (SET은 LIST를 아이템으로 받지 못한다)

 

가장 중요한 왼쪽으로 움직이는 함수는 다음과 같다

def move_left(board):  # 왼쪽으로 움직임
    new_board = []
    max_num = 0
    used = False
    for i in range(n):
        new_row = list()
        for num in board[i]:
            if num:
                max_num = max(max_num, num)  # 최댓값 갱신
                if new_row and not used and new_row[-1] == num:  # 마지막 숫자가 사용되지 않았고 같다면
                    new_row[-1] *= 2  # 마지막 숫자 2배 처리
                    max_num = max(max_num, new_row[-1])  # 최댓값 갱신
                    used = True
                else:
                    new_row.append(num)  # 숫자와 False(미사용)을 넣는다
                    used = False
        new_row += [0] * (n - len(new_row))  # 0 채우기
        new_board.append(tuple(new_row))

    return tuple(new_board), max_num

각 행의 숫자들을 왼쪽으로 이동한 후에 이동이 완료된 각 행들을 합치는 과정으로 동작한다.

각 행의 숫자들을 순회하는데 0은 무시한다. 0이 차지하는 공간은 왼쪽으로 이동할 때 채워지기 때문에 0은 무시한 후에 이동이 완료한 후에 뒤에 붙여주게 된다.

그래서 new_row 리스트에는 0이 아닌 2의 배수만 들어가고, 마지막에 들어간 숫자를 아직 사용하지 않았다면 2배로 만든다. 그리고 2배가 된 마지막 숫자는 사용된 것이기 때문에 used 변수를 True로 변경한다.

만약 마지막 숫자가 이미 사용되었거나, 새로 넣으려는 숫자와 다른 경우는 그냥 new_row에 추가하고, 사용되지 않은 새 숫자가 들어온 것이기 때문에 used를 False로 바꿔준다.

위 과정이 끝나면 앞서 말했듯이 부족한 만큼 0을 채운다. (N - new_row의 크기)

위 과정이 완료되면 한 행에서의 작업이 완료된다. 이를 new_board에 추가한다.

 

def user_input():
    global n, graph
    n = int(input())
    graph = [list(map(int, input().split())) for _ in range(n)] if n > 1 else [int(input())]

BFS 함수를 보기 전에 사용자가 입력하는 부분을 먼저 살펴보자.

graph를 만드는 부분이 중요한데, 만약 N이 1이라면 예외 케이스가 된다. 왜냐하면 [[2, 2], [4, 8]] 과 같은 형태로 만들어지는 것이 일반적인 형태인데 N이 1일 때는 [16] 과 같이 만들어져야 하는데 조건문으로 처리하지 않으면 [[16]]과 같이 만들어지기 때문이다.

 

마지막으로 BFS 함수를 살펴보면 다음과 같다.

def bfs():
    if n == 1:
        print(graph[0])
        return
    q = deque()
    answer = 0
    q.append((tuple(map(tuple, graph)), 0, 0))
    cache = set()

    while q:
        board, max_num, count = q.popleft()
        cache.add(board)
        if max_num > answer: answer = max_num
        for i in range(4):
            new_board, new_max_num = move(board, i)
            if count < 5 and new_board not in cache:
                q.append((new_board, new_max_num, count + 1))
    print(answer)

사용자 입력 부분에서 처리한 N이 1일 때는 특수한 형태를 띄고, 바로 답을 구할 수 있기 때문에 값을 출력하고 종료한다.

큐에는 게임 판과 현재 최댓값, 그리고 이동한 횟수를 저장한다.

cache는 SET으로 만들었다. SET에 넣기 위해서는 LIST가 아닌 TUPLE이 되어야 한다.

반복문으로 상, 하, 좌, 우로 이동하며 이동한 횟수가 5보다 작을 때만 큐에 넣는다. 이 과정에서 계속해서 최댓값을 갱신한다.

모든 과정이 끝나면 answer에 담겨 있는 최댓값을 출력하고 종료한다.

 

전체 코드

from collections import deque

n, graph = None, None


def user_input():
    global n, graph
    n = int(input())
    graph = [list(map(int, input().split())) for _ in range(n)] if n > 1 else [int(input())]


def flip(board):
    return tuple([tuple(row[::-1]) for row in board])


def turn_right(board):
    return tuple(map(tuple, zip(*board[::-1])))


def turn_left(board):
    ret = [[0] * n for _ in range(n)]
    for x in range(n):
        for y in range(n):
            ret[n - 1 - y][x] = board[x][y]
    return tuple(tuple(row) for row in ret)


def move_left(board):  # 왼쪽으로 움직임
    new_board = []
    max_num = 0
    used = False
    for i in range(n):
        new_row = list()
        for num in board[i]:
            if num:
                max_num = max(max_num, num)  # 최댓값 갱신
                if new_row and not used and new_row[-1] == num:  # 마지막 숫자가 사용되지 않았고 같다면
                    new_row[-1] *= 2  # 마지막 숫자 2배 처리
                    max_num = max(max_num, new_row[-1])  # 최댓값 갱신
                    used = True
                else:
                    new_row.append(num)  # 숫자와 False(미사용)을 넣는다
                    used = False
        new_row += [0] * (n - len(new_row))  # 0 채우기
        new_board.append(tuple(new_row))

    return tuple(new_board), max_num


def move_right(board):
    new_board, max_num = move_left(flip(board))
    return flip(new_board), max_num


def move_down(board):
    new_board, max_num = move_left(turn_right(board))
    return turn_left(new_board), max_num


def move_up(board):
    new_board, max_num = move_left(turn_left(board))
    return turn_right(new_board), max_num


def move(board, i):
    if i == 0:
        return move_up(board)
    elif i == 1:
        return move_down(board)
    elif i == 2:
        return move_left(board)
    elif i == 3:
        return move_right(board)


def bfs():
    if n == 1:
        print(graph[0])
        return
    q = deque()
    answer = 0
    q.append((tuple(map(tuple, graph)), 0, 0))
    cache = set()

    while q:
        board, max_num, count = q.popleft()
        cache.add(board)
        if max_num > answer: answer = max_num
        for i in range(4):
            new_board, new_max_num = move(board, i)
            if count < 5 and new_board not in cache:
                q.append((new_board, new_max_num, count + 1))
    print(answer)


user_input()

bfs()

 

채점 결과