이번 문제는 삼성 기출 문제로, 백트레킹을 통해 해결하였다. 처음 코드는 30분만에 작성하였고, 질문하기 란에 있는 테스트케이스들도 모두 맞았다. 제출한 결과, 85%에서 오답처리되었고, 이 부분에 대해 아무리 코드를 뜯어보고 찾아보았지만 찾지 못하였다. 로직은 주어진 방향으로 블럭들을 모두 밀어내고, 다시 순회하며 밀어낸 블럭들 중 같은 수인 것들끼리 합치도록 하였다. 결국은 긴 고민 끝에 코드를 다시 작성하기로 하였고, 이번에는 이 과정을 묶어서 진행하였다. 임시 변수에 값을 담아두고, 현재 칸이 비어있다면 임시 변수의 값을 넣어주고, 현재 칸이 임시변수와 같다면 2배를 해주고, 현재 인덱스를 이동시켜주는 방식으로 작성하였다.

Code

초기 코드 (85% 오답)

import copy
n = int(input())
grid = [list(map(int, input().split())) for _ in range(n)]
answer = 0
def move(d):
    tmp = [[0 for _ in range(n)] for _ in range(n)]
    result = [[0 for _ in range(n)] for _ in range(n)]
    if d == 0:
        for i in range(n):
            idx = 0
            for j in range(n):
                if grid[j][i]:
                    tmp[idx][i] = grid[j][i]
                    idx += 1
        for i in range(n):
            idx = 0
            cur = 0
            while idx < n-1:
                if tmp[idx][i] == tmp[idx+1][i]:
                   result[cur][i] = tmp[idx][i]*2
                   idx += 2
                   cur += 1
                else:
                    result[cur][i] = tmp[idx][i]
                    idx += 1
                    cur += 1
            result[cur][i] = tmp[n-1][i]
    elif d == 1:
        for i in range(n):
            idx = n - 1
            for j in range(n-1, -1, -1):
                if grid[j][i]:
                    tmp[idx][i] = grid[j][i]
                    idx -= 1
        for i in range(n):
            idx = n-1
            cur = n-1
            while idx > 0:
                if tmp[idx][i] == tmp[idx-1][i]:
                    result[cur][i] = tmp[idx][i]*2
                    idx -= 2
                    cur -= 1
                else:
                    result[cur][i] = tmp[idx][i]
                    idx -= 1
                    cur -= 1
            result[cur][i] = tmp[0][i]
    elif d == 2:
        for i in range(n):
            idx = 0
            for j in range(n):
                if grid[i][j]:
                    tmp[i][idx] = grid[i][j]
                    idx += 1
        for i in range(n):
            idx = 0
            cur = 0
            while idx < n-1:
                if tmp[i][idx] == tmp[i][idx+1]:
                    result[i][cur] = tmp[i][idx]*2
                    idx += 2
                    cur += 1
                else:
                    result[i][cur] = tmp[i][idx]
                    idx += 1
                    cur += 1
            result[i][cur] = tmp[i][n-1]
    elif d == 3:
        for i in range(n):
            idx = n - 1
            for j in range(n-1, -1, -1):
                if grid[i][j]:
                    tmp[i][idx] = grid[i][j]
                    idx -= 1
        for i in range(n):
            idx = n-1
            cur = n-1
            while idx > 0:
                if tmp[i][idx] == tmp[i][idx-1]:
                    result[i][cur] = tmp[i][idx]*2
                    idx -= 2
                    cur -= 1
                else:
                    result[i][cur] = tmp[i][idx]
                    idx -= 1
                    cur -= 1
            result[i][cur] = tmp[i][0]
    return result
def find_max():
    result = 0
    for i in range(n):
        result = max(result, max(grid[i]))
    return result
def try_move(cnt):
    global answer, grid
    answer = max(answer, find_max())
    if cnt == 5:
        return
    tmp_grid = copy.deepcopy(grid)
    for i in range(4):
        grid = copy.deepcopy(move(i))
        try_move(cnt+1)
        grid = copy.deepcopy(tmp_grid)
try_move(0)
print(answer)

정답 코드

import copy
n = int(input())
grid = [list(map(int, input().split())) for _ in range(n)]
answer = 0
def move_num(d):
    if d == 0:
        for j in range(n):
            idx = 0
            for i in range(1, n):
                if grid[i][j]:
                    tmp = grid[i][j]
                    grid[i][j] = 0
                    if grid[idx][j] == 0:
                        grid[idx][j] = tmp
                    elif grid[idx][j] == tmp:
                        grid[idx][j] = tmp * 2
                        idx += 1
                    else:
                        idx += 1
                        grid[idx][j] = tmp
    elif d == 1:
        for j in range(n):
            idx = n - 1
            for i in range(n - 2, -1, -1):
                if grid[i][j]:
                    tmp = grid[i][j]
                    grid[i][j] = 0
                    if grid[idx][j] == 0:
                        grid[idx][j] = tmp
                    elif grid[idx][j] == tmp:
                        grid[idx][j] = tmp * 2
                        idx -= 1
                    else:
                        idx -= 1
                        grid[idx][j] = tmp
    elif d == 2:
        for i in range(n):
            idx = 0
            for j in range(1, n):
                if grid[i][j]:
                    tmp = grid[i][j]
                    grid[i][j] = 0
                    if grid[i][idx] == 0:
                        grid[i][idx] = tmp
                    elif grid[i][idx] == tmp:
                        grid[i][idx] = tmp * 2
                        idx += 1
                    else:
                        idx += 1
                        grid[i][idx] = tmp
    elif d == 3:
        for i in range(n):
            idx = n - 1
            for j in range(n - 2, -1, -1):
                if grid[i][j]:
                    tmp = grid[i][j]
                    grid[i][j] = 0
                    if grid[i][idx] == 0:
                        grid[i][idx] = tmp
                    elif grid[i][idx] == tmp:
                        grid[i][idx] = tmp * 2
                        idx -= 1
                    else:
                        idx -= 1
                        grid[i][idx] = tmp
def find_max():
    result = 0
    for i in range(n):
        result = max(result, max(grid[i]))
    return result
def try_move(cnt):
    global answer, grid
    answer = max(answer, find_max())
    if cnt == 5:
        return
    tmp_grid = copy.deepcopy(grid)
    for i in range(4):
        move_num(i)
        try_move(cnt+1)
        grid = copy.deepcopy(tmp_grid)
try_move(0)
print(answer)