12100 - 2048 (Easy)

 

---

 

문제

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

12100번: 2048 (Easy)

 

풀이

완전탐색이 조금 곁들여진 구현문제이다.

 

우선 최대 5번을 움직여야하니 경우의 수를 모두 만들어주면 된다. 난 itertools 의 product를 사용해서 경우의 수를 만들었고, 각자 숫자와 방향을 매칭해서 생각했다.

( 0, ← ) , ( 1, ↑ ) , ( 2, → ) , ( 3, ↓ )

 

이후에 숫자를 어떻게 합칠지 말지를 생각했는데, 행 단위로 생각했고, 왼쪽으로 누를경우를 먼저 생각했다.

 

1. 배열 왼쪽부터 검사해서 가장 가까운 요소를 최대한 왼쪽으로 붙인다.

 

2.  그 다음으로 왼쪽에 가까운 요소를 찾아보고,

 2 - 1. 1번에서 붙인 요소와 값이 같다면 합쳐주고, 해당 위치는 0으로 바꿔준다.

 2 - 2. 만약 요소가 다르다면 왼쪽으로 그냥 붙여주고 2번 과정을 반복한다.

 

이 부분의 코드를 살펴보면 이렇다.

# 값을 가장 왼쪽으로 붙인다.
while i <= n:
    # 값을 왼쪽으로 땡겨온다.
    for j in range(i, n):
        # 유효한 값이라면
        if arr[j] != 0 :
            arr[i] = arr[j]
            if i != j:
                arr[j] = 0
            break

arr = [2, 0, 2, 4] 일 경우

 

arr[0]의 위치값을 찾기위해 j가 돌게된다.  j가 0일때 arr[j] 은  바로 찾기 때문에 arr[0]의 값이 그대로 들어간다. 단, 이 경우에는 i와 j가 같기 때문에 실상으로는 땡겨준게 아니다. 그렇기 때문에 0을 처리하면 안된다.

 

기본적인 아이디어는 이렇다. 대신 이 문제의 귀찮은 점은 오른쪽 방향 및 위아래 방향을 눌렀을때이다.

 

나는 오른쪽 방향은 배열을 뒤집어줘서 똑같은 로직으로 작성했고, 위 아래 같은 경우에는 반시계 방향으로 회전한 다음 처리했다. 반시계 방향으로 회전할경우 위키를 누르는것은 왼쪽키를 누르는것과 같고 아래키를 누르는것은 오른쪽 키를 누르는것과 같기 때문이다.  열을 추출해서 위 아래를 처리할까 했으나, 손이 더 많이 갈 거 같아 배열 회전으로 처리했다.

 

코드

import copy
import itertools
from sys import stdin

def rotate(arr, dir):

    # 시계 방향
    if dir == 0:
        return list(map(list, zip(*arr[::-1])))

    # 반시계 방향
    if dir == 1:
        return list(map(list, zip(*arr)))[::-1]

def move(temp):
    global n
    i = 0
    arr = copy.deepcopy(temp)
    # 값을 가장 왼쪽으로 붙인다.
    while i <= n:
        # 값을 왼쪽으로 땡겨온다.
        for j in range(i, n):
            # 유효한 값이라면
            if arr[j] != 0 :
                arr[i] = arr[j]
                if i != j:
                    arr[j] = 0
                break

        # 같은 값이 있는지 체킹
        for j in range(i+1, n):
            if arr[j] == 0: continue

            if arr[i] == arr[j]:
                arr[i] *= 2
                arr[j] = 0
                break

            if arr[i] != arr[j]:
                arr[i+1] = arr[j]
                if i+1 != j:
                    arr[j] = 0
                break
        i += 1

    return arr

# # initialize
n = int(input())
origin_board = [ list(map(int, stdin.readline().rstrip().split())) for _ in range(n) ]
move_list = list(itertools.product([0, 1, 2, 3], repeat=5))

answer = 0
for m in move_list:
    board = copy.deepcopy(origin_board)
    for val in m:

        # 위 아래일경우 배열을 회전시켜준다.
        if val == 1 or val == 3:
            board = rotate(board, 1)

        if val == 0 or val == 1:
            for i in range(n):
                board[i] = move(board[i])

        # 오른쪽으로 간다면 역방향
        if val == 2 or val == 3:
            for i in range(n):
                board[i] = move(list(reversed(board[i])))

    answer = max(answer, max(map(max, board)))

print(answer)

 

후기

 

아이디어는 괜찮았는데, 몇몇 예외처리때문에 또 시간을 많이 잡아먹었다. 또한 2차원 배열 최댓값을 찾거나, 배열을 뒤집는 거, 배열을 회전하는 등의 테크닉이 검색없이는 빡세다.. 주로 사용하는 테크닉들은 정리해두자.