[BOJ] 12100번. 2048(Easy)

www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

풀이

• DFS를 사용하는 문제
• 모든 경우의수를 다 시도해봄.
• max_val, board를 글로벌 변수로 두고 사용.
• 해당 위치에서 숫자가 바뀌었는지 안바뀌었는지 정보도 저장해야함.
  • 4, 4, 4, 4 -> 오른쪽으로 -> 0, 0, 8, 8이 되어야함 (cf. 0, 0, 8, 8에서 0, 0, 0, 16이 되면 안됨.)

# 입력 받음
n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]

# 방향 배열 : 위, 오른쪽, 아래, 왼쪽
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

max_val, count = -1, 0

def move(board, dir):
    if dir == 0 or dir == 3:
        start_idx, end_idx, diff = 0, n, 1
    else:
        start_idx, end_idx, diff = n-1, -1, -1

    ch = [[1 for _ in range(n)] for _ in range(n)]
    for i in range(start_idx, end_idx, diff):
        for j in range(start_idx, end_idx, diff):
            if board[i][j] == 0:
                continue

            x, y = i, j
            # 다음칸 좌표
            next_x = i + dx[dir]
            next_y = j + dy[dir]
            # 현재 좌표는 다로 저장하고, 0으로 바꿔줌
            val = board[i][j]
            board[i][j] = 0

            while 0 <= next_x <= n-1 and 0 <= next_y <= n-1:
                # 보드의 다음 좌표값이 0이면 계속 이동
                if board[next_x][next_y] == 0:
                    x, y = next_x, next_y
                    next_x, next_y = next_x + dx[dir], next_y + dy[dir]

                # 다음 칸의 블록 숫자와 기존 블록 숫자가 같음. 그리고 다음 칸에서 숫자바뀜이 안일어났는지 확인.(중복체크)
                elif board[next_x][next_y] == val and ch[next_x][next_y]:
                    ch[next_x][next_y] = 0
                    x, y = next_x, next_y
                    break
                else:
                    break
            board[x][y] = board[x][y] + val
    return board

def DFS(count):
    global max_val, board
    # 5번째가 됬을때 max_val 업데이트함.
    if count == 5:
        max_val = max(max_val, max([max(i) for i in board]))

    else:
        for i in range(4):
            b = [x[:] for x in board]
            board = move(board, i)
            DFS(count + 1)
            board = [x[:] for x in b]

DFS(0)
print(max_val)