http://boj.kr/12100 

 

12100번: 2048 (Easy)

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

www.acmicpc.net

 

 

보드는 동서남북으로 기울일 수 있으므로 임의로 각 방향마다 0~4까지 번호를 정해주었다. 

그리고 미리 가능한 방향들의 경우의 수를 모두 구한 후에 그대로 기울여본 후 최대값을 갱신하는 방식으로 진행했다.

가능한 방향들의 경우의 수를 구하는 방법은, 뽑을 수 있는 가짓수(방향)는 4개이고 총 5개를 뽑아야 하므로 4개 중 5개를 중복을 허용하는 순열로 뽑았다. 기울이는 순서에 따라 결과도 달라지므로 조합이 아니라 순열로 뽑아야 한다.

 

한 가지 방향으로 기울이는 방법만 알면 나머지 방향은 조금씩만 수정하면 되므로, 위로 기울이는 방법을 보자.

위로 기울인다는 것은 (0, 0) 원소 입장에서 (1, 0) 에 있는 원소들을 땡겨온다는 뜻이다. 

여기서 두 케이스가 있을 수 있다. 기준 원소 (0, 0)의 값이 0인 케이스와 0이 아닌 케이스가 있을 수 있다.

먼저 값이 0이면 다음 행에 있는 것들 중 0이 아닌 값을 찾아서 가져와야 한다. 즉, 먼저 밀어주어야 한다. 

 

이제 기준 원소의 값이 0이 아니게 되었으면, 거기서부터 다시 그 다음 행에서 0이 아닌 값들을 가져와서 비교한다.

비교해서 같은 값이면 합쳐준다. 다른 값이면 아무 행동도 하지 않는다. 어차피 다음 반복문에서 그 원소를 땡겨오거나 사용하게 될 것이다.

 

남쪽으로 밀어줄 때는 기준 원소가 0에서 시작하는 것이 아니라 N-1에서 시작해서 1로 끝난다는 점이 달라진다.

마지막이 (1, y)가 되고 비교 원소가 (0, y)가 될 것이므로 마지막 row가 0이 아닌 1이 된다. 마지막 row를 0으로 두면 그 다음 비교 원소가 -1이 되므로, out of index가 되거나 비교문을 한번 넣어줘야 한다.

 

주의해야 할 점은 한 번의 기울임마다 두 번 합쳐질 수 없다는 뜻이지, 한번 합쳐진 원소는 두번 다시 못 합쳐진다는 뜻이 아니므로 한번 기울여진 적이 있음을 체크하는 배열을 계속 초기화해줘야 된다는 점이다. (여기서는 added를 계속 새로 선언했다.)

 

import sys
from copy import deepcopy


def solve(selected):
    board = deepcopy(board_o)
    for direct in selected:
        added = [[False for _ in range(N)] for _ in range(N)]
        if direct == 0:  # UP
            for r in range(N-1):
                for c in range(N):
                    next_r = r + 1
                    
                    # 기준 원소의 값이 0일 때 -> 0이 아닌 값을 찾아서 땡겨온다.
                    if board[r][c] == 0:
                        while next_r < N:
                            if board[next_r][c] == 0:
                                next_r += 1
                            else:
                                board[r][c] = board[next_r][c]
                                board[next_r][c] = 0
                                break
                                
                    # 기준 원소의 값이 0이 아닐 때 -> 다음 줄에 있는 원소 중 0이 아닌 것을 땡겨온다.
                    while next_r < N:
                        if board[next_r][c] == 0:
                            next_r += 1
                        else:  # 0이 아닌 것을 땡겨 왔으면 비교 후 같으면 합쳐준다.
                            if board[r][c] == board[next_r][c] \
                                    and not added[next_r][c] and not added[r][c]:
                                board[r][c] = board[r][c] * 2
                                board[next_r][c] = 0
                                added[r][c] = True
                                added[next_r][c] = False
                            break
        elif direct == 1:  # DOWN
            for r in reversed(range(1, N)):
                for c in range(N):
                    next_r = r - 1
                    if board[r][c] == 0:
                        while next_r >= 0:
                            if board[next_r][c] == 0:
                                next_r -= 1
                            else:
                                board[r][c] = board[next_r][c]
                                board[next_r][c] = 0
                                break
                    while next_r >= 0:
                        if board[next_r][c] == 0:
                            next_r -= 1
                        else:
                            if board[r][c] == board[next_r][c] \
                                    and not added[next_r][c] and not added[r][c]:
                                board[r][c] = board[r][c] * 2
                                board[next_r][c] = 0
                                added[r][c] = True
                                added[next_r][c] = False
                            break
        elif direct == 2:  # LEFT
            for r in range(N):
                for c in range(N - 1):
                    next_c = c + 1
                    if board[r][c] == 0:
                        while next_c < N:
                            if board[r][next_c] == 0:
                                next_c += 1
                            else:
                                board[r][c] = board[r][next_c]
                                board[r][next_c] = 0
                                break
                    while next_c < N:
                        if board[r][next_c] == 0:
                            next_c += 1
                        else:
                            if board[r][c] == board[r][next_c] \
                                    and not added[r][next_c] and not added[r][c]:
                                board[r][c] = board[r][c] * 2
                                board[r][next_c] = 0
                                added[r][c] = True
                                added[r][next_c] = False
                            break
        elif direct == 3:  # Right
            for r in range(N):
                for c in reversed(range(1, N)):
                    next_c = c - 1
                    if board[r][c] == 0:  # 땡기기
                        while next_c >= 0:
                            if board[r][next_c] == 0:
                                next_c -= 1
                            else:
                                board[r][c] = board[r][next_c]
                                board[r][next_c] = 0
                                break
                    while next_c >= 0:
                        if board[r][next_c] == 0:
                            next_c -= 1
                        else:
                            if board[r][c] == board[r][next_c] \
                                    and not added[r][next_c] and not added[r][c]:
                                board[r][c] = board[r][c] * 2
                                board[r][next_c] = 0
                                added[r][c] = True
                                added[r][next_c] = False
                            break

    ret = max([max(r) for r in board])
    return ret


def dfs(count, selected):
    global maxRet
    if count == 5:
        maxRet = max(maxRet, solve(selected))
        return
    for i in range(4):
        dfs(count+1, selected+[i])
    return maxRet


maxRet = 0
input = sys.stdin.readline
N = int(input())
board_o = [list(map(int, input().split())) for _ in range(N)]
print(dfs(0, []))

 

'알고리즘 > 브루트포스' 카테고리의 다른 글

16637. 괄호 추가하기 (2)  (0) 2020.05.12
16637번. 괄호 추가하기  (0) 2020.05.11
17609번. 회문  (0) 2020.04.19
12100. 2048 (Easy)  (0) 2020.01.07
2231. 분해합  (0) 2019.11.20

+ Recent posts