문제 링크

2048 (Easy)
킹받는 (Easy) ,,^^ 누구맘대로 이지야 ㅠ

문제 설명

다들 한번씩 플레이해봤을 2048게임과 같은 방식으로 동작하되 새로운 블록이 추가되지는 않는다.
N*N크기의 보드 위의 블록을 상하좌우로 이동시키는데 이때 같은 값을 가지는 블록 두개가 충돌 시 1개로 합쳐진다. 0은 빈칸을 나타내고, 나머지 값은 2이상 2048 이하인 2의 제곱꼴이다.
최대 5번을 이동시켜서 얻을 수 있는 최대값은?

문제 풀이

시도 1

처음에는 이런 식으로 접근했다. move()를 이용해서 dir방향으로 보드 위의 각 블록을 이동시키고, dfs를 이용해서 모든 경우의 수를 찾으려고 했다.
하지만 테스트 케이스를 돌려본 결과 생각하지 못했던 부분이
1. 이미 이번 회차에 합쳐진 블록은 다시 합칠 수 없음

문제 설명에도 나와있듯이,,^^
2. 아래로 혹은 오른쪽으로부터 합치는 경우 (0,0)~(N-1,N-1)의 순서로 순회하면 안됨

테스트케이스의 경우에, 왼쪽, 오른쪽으로 밀었을때 각각 저렇게 나와야 한다. 하지만 (0,0)부터 순회해서 이동시키는 경우에는 우측으로 밀었을때의 결과가 [[0,4,2],[0,8,4],[0,16,8]]과 같이 나온다.
아래로 혹은 오른쪽으로 합치는 경우에는 (N-1, N-1)부터 (0,0)까지의 순서로 이동시켜야 한다.

시도 2

import sys
import copy

input = sys.stdin.readline

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
N = int(input())
answer = 0
board = []
for _ in range(N):
    board.append(list(map(int, input().split())))

def in_bound(x, y):
    if x in range(0,N) and y in range(0,N):
        return True
    else:
        return False

def move(board, dir):
    merged = [[0]*N for _ in range(N)]
    if dir % 2 == 0:
        start, end, inc = 0, N, 1
    else:
        start, end, inc = N-1, -1, -1
    # 각각의 칸에 대해서
    for i in range(start, end, inc):
        for j in range(start, end, inc):
            if board[i][j] != 0:
                x, y = i, j
                nx, ny = x + dx[dir], y + dy[dir]
                while in_bound(nx, ny):
                    # 빈칸이면
                    if board[nx][ny] == 0:
                        board[nx][ny] = board[x][y]
                        board[x][y] = 0
                        x, y = nx, ny
                        nx, ny = x + dx[dir], y + dy[dir]
                    # 같은 숫자를 만나면
                    elif board[nx][ny] == board[x][y]:
                        if not merged[nx][ny]:
                            board[nx][ny] += board[x][y]
                            board[x][y] = 0
                            merged[nx][ny] = 1
                        break
                    # 다른 숫자를 만나면
                    else:
                        break
    

def dfs(board, count):
    #print(count, board)
    global answer
    if count >= 5:
        max_val = 0
        for i in range(N):
            max_val = max(max_val, max(board[i]))
        answer = max(answer, max_val)
        return
    for i in range(4):
        new_board = copy.deepcopy(board)
        move(new_board, i)
        #이동 가능하면
        if new_board != board:
            dfs(new_board, count+1)
        #더 이상 이동이 불가능하면 -> 최대값 갱신 
        else:
            max_val = 0
            for j in range(N):
                max_val = max(max_val, max(board[j]))
            answer = max(answer, max_val)


dfs(board, 0)
print(answer)

느낀점

쉽지 않았넵 ,, 그래도 이번엔 다른거 참고 안하고 풀었다 ,,^__^ 다른 사람들은 어떻게 풀었는지 찾아봤는데 비슷한 로직으로 푼거 같다 ,,
코드 짜기 전에 수도코드를 좀 더 진득하게 생각하고 자세히 써본 다음에 푸는 습관을 들여야 겠다,, 그리고 문제도 똑바로 읽긔