백준 12100 2048(Easy) - (Python)

문제

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

 

나의 접근법

처음에는 알고리즘이 바로 생각안나서 알고리즘만 보고 힌트를 얻었습니다. 백트래킹과 브루트포스를 보고 DFS로 depth가 5일 때 종료해주면 된다고 생각해서 상,하,좌,우로 이동하는 것만 잘 만들어 주면 쉽게 해결할 수 있다고 생각했습니다.

첫번째 코드

def move(arr, i):
    # 위로 이동
    if i == 0:
        for y in range(N):
            for x in range(1, N - 1):
                if arr[x][y] == arr[x + 1][y]:
                    arr[x][y] = arr[x][y] + arr[x + 1][y]
                    arr[x + 1][y] = 0
                elif arr[x][y] == 0:
                    arr[x][y] = arr[x + 1][y]
                    arr[x + 1][y] = 0
    # 아래로 이동
    elif i == 1:
        for y in range(N):
            for x in range(N - 1, 0, -1):
                # 아래로 이동
                if arr[x][y] == arr[x - 1][y]:
                    arr[x][y] = arr[x][y] + arr[x - 1][y]
                    arr[x - 1][y] = 0
                elif arr[x][y] == 0:
                    arr[x][y] = arr[x - 1][y]
                    arr[x - 1][y] = 0
    # 왼쪽으로 이동
    elif i == 2:
        for x in range(N):
            for y in range(N - 1):
                if arr[x][y] == arr[x][y + 1]:
                    arr[x][y] = arr[x][y] + arr[x][y + 1]
                    arr[x][y + 1] = 0
                elif arr[x][y] == 0:
                    arr[x][y] = arr[x][y + 1]
                    arr[x][y + 1] = 0
    # 오른쪽으로 이동
    elif i == 3:
        for x in range(N):
            for y in range(N - 1, 0, -1):
                if arr[x][y] == arr[x][y - 1]:
                    arr[x][y] = arr[x][y] + arr[x][y - 1]
                    arr[x][y - 1] = 0
                elif arr[x][y] == 0:
                    arr[x][y] = arr[x][y - 1]
                    arr[x][y - 1] = 0

    return arr

def dfs(arr, cnt):
    global ans
    if cnt == 5:
        for i in range(N):
            for j in range(N):
               ans = max(ans, arr[i][j])
        return

    for i in range(4):
        tempArr = [i[:] for i in arr]
        tempArr = move(tempArr, i)
        dfs(tempArr, cnt+1)

N = int(input())
graph = []
ans = -1
for i in range(N):
    graph.append(list(map(int, input().split())))

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

dfs(graph, 0)
print(ans)

저는 먼저 매 depth마다 방향마다 상 하 좌 우로 이동을 시키고 그 이동시킨 맵을 return 하여 dfs에 depth와 함께 넣어주었습니다. 

하지만 언제나 그렇듯 한번에 맞지 않았습니다. 저는 디버그를 해보고 지도 정보인 arr을 옮겨보며 정답을 맞추려고 했습니다. 하지만 결국 답을 찾지 못하여 다른 사람들의 답을 보고 틀린 곳을 찾으려 했습니다.

제 move 함수가 살짝 달랐습니다. 한칸 한칸씩 모든 arr을 방문하여 0이 아닌 경우 한칸씩 위로올리면 된다고 쉽게 생각했습니다. 하지만 이렇게 할 경우 상 하 좌 우 한번당 한 칸씩 밖에 이동을 하지 못했고 정답은 한칸이 아니라 0이 아닌 숫자를 만날때 까지 이동해야 합니다.

 

저는 위 차이점을 찾아 코드를 아래와 같이 변경하여 정답을 맞을 수 있었습니다.

 

두번째 코드

def move(arr, i):
    # 위로 이동 #한 칸씩 가는 게 아니라 0 안 만날 때까지
    if i == 0:
        for y in range(N):
            top = 0
            for x in range(1, N):
                if arr[x][y]:
                    temp = arr[x][y]
                    arr[x][y] = 0
                    if arr[top][y] == temp:
                        arr[top][y] = arr[top][y] + temp
                        top += 1
                    elif arr[top][y] == 0:
                        arr[top][y] = temp
                    else:
                        top += 1
                        arr[top][y] = temp #
    # 아래로 이동
    elif i == 1:
        for y in range(N):
            bot = N-1
            for x in range(N-2, -1, -1):
                if arr[x][y]:
                    temp = arr[x][y]
                    arr[x][y] = 0
                    if arr[bot][y] == temp:
                        arr[bot][y] = arr[bot][y] + temp
                        bot -= 1
                    elif arr[bot][y] == 0:
                        arr[bot][y] = temp
                    else:
                        bot -= 1
                        arr[bot][y] = temp  #
    # 왼쪽으로 이동
    elif i == 2:
        for x in range(N):
            left = 0
            for y in range(1, N):
                if arr[x][y]:
                    temp = arr[x][y]
                    arr[x][y] = 0
                    if arr[x][left] == temp:
                        arr[x][left] = arr[x][left] + temp
                        left += 1
                    elif arr[x][left] == 0:
                        arr[x][left] = temp
                    else:
                        left += 1
                        arr[x][left] = temp  #
    # 오른쪽으로 이동
    elif i == 3:
        for x in range(N):
            right = N - 1
            for y in range(N - 2, -1, -1):
                if arr[x][y]:
                    temp = arr[x][y]
                    arr[x][y] = 0
                    if arr[x][right] == temp:
                        arr[x][right] = arr[x][right] + temp
                        right -= 1
                    elif arr[x][right] == 0:
                        arr[x][right] = temp
                    else:
                        right -= 1
                        arr[x][right] = temp  #
    return arr

def dfs(arr, cnt):
    global ans
    if cnt == 5:
        for i in range(N):
            for j in range(N):
               ans = max(ans, arr[i][j])
        return

    for i in range(4):
        tempArr = [i[:] for i in arr]
        tempArr = move(tempArr, i)
        dfs(tempArr, cnt+1)

N = int(input())
graph = []
ans = -1
for i in range(N):
    graph.append(list(map(int, input().split())))

dfs(graph, 0)
print(ans)

 

후기

이번에도 처음부터 끝까지 제 스스로 완벽하게 코드를 짜서 정답을 맞추지 못했습니다. 계속 이렇게 푸는게 맞는지 의문이 들 정도로 실력이 안느는 것 같습니다. 그래서 그런가 매일 코테를 준비하는 것이 너무 고되고 힘드네요.

아직 실력이 많이 부족한 것 같지만 아직 포기하기는 너무 이른 것 같고 제 자신한테 지는게 싫습니다.

최대한 붙잡고 늘어져서 삼성 코테 꼭 붙고 오겠습니다.

일단 삼성 기출을 최대한 풀고 모르면 다 외우는 방식으로 해야겠습니다.