[백준 12100번] 2048(Easy) - 구현 / 시뮬레이션 / 완전탐색 / 백트래킹

12100번: 2048 (Easy)

# 4x4 크기 보드
# 한번 이동할 때 보드 위에 있는 모든 블록이 상-하-좌-우 중 하나로 이동

# 같은 값을 갖는 두 블록이 충돌하면 합쳐짐
# 한번의 이동에서 합쳐진 블록은 다시 합쳐질 수 X

import copy

n = int(input())

zone = [list(map(int,input().split())) for _ in range(n)]

max_value = -1

# 왼쪽으로 이동시키는 함수
def moveLeft():
    marged = [[False]*n for _ in range(n)]
    
    for i in range(n): # 행 
        for j in range(1,n): # 열
            if zone[i][j] == 0:
                continue
            for k in range(j-1,-1,-1):
                if zone[i][k] == zone[i][k+1] and not marged[i][k]:
                    zone[i][k] *= 2
                    zone[i][k+1] = 0
                    marged[i][k] = True
                    break
                elif zone[i][k] == 0:
                    zone[i][k] = zone[i][k+1]
                    zone[i][k+1]= 0 
                else:
                    break
    return

def moveRight():
    marged = [[False]*n for _ in range(n)]

    for i in range(n):
        for j in range(n-2,-1,-1):
            if zone[i][j] == 0:
                continue
            for k in range(j+1,n):
                if zone[i][k] == zone[i][k-1] and not marged[i][k]:
                    zone[i][k] *= 2
                    zone[i][k-1] = 0
                    marged[i][k] = True
                    break
                elif zone[i][k] == 0:
                    zone[i][k] = zone[i][k-1]
                    zone[i][k-1] = 0
                else:
                    break
    return

# 위로 이동시키는 함수
def moveUp():
    marged = [[False]*n for _ in range(n)]

    for i in range(n): # 열
        for j in range(1,n): # 행
            if zone[j][i] == 0: # 빈칸인 경우 무시
                continue
            for k in range(j-1,-1,-1): 
                if zone[k][i] == zone[k+1][i] and not marged[k][i]:
                    zone[k][i] *= 2
                    zone[k+1][i] = 0
                    marged[k][i] = True
                    break
                elif zone[k][i] == 0: # 빈칸을 만난 경우
                    zone[k][i] = zone[k+1][i]
                    zone[k+1][i] = 0
                else:
                    break
    return
    
# 아래로 이동시키는 함수
def moveDown():
    marged = [[False]*n for _ in range(n)]
    
    for i in range(n):
        for j in range(n-2,-1,-1):
            if zone[j][i] == 0:
                continue
            for k in range(j+1,n):
                if zone[k][i] == zone[k-1][i] and not marged[k][i]:
                    zone[k][i] *= 2
                    zone[k-1][i] = 0
                    marged[k][i] = True
                    break
                elif zone[k][i] == 0:
                    zone[k][i] = zone[k-1][i]
                    zone[k-1][i] = 0
                else:
                    break
    return

# 최댓값을 찾는 함수
def searchMaxValue():
    global max_value
    for i in range(n):
        for j in range(n):
            if zone[i][j] > max_value:
                max_value = zone[i][j]

def dfs(depth):
    
    global zone

    searchMaxValue()
    
    if depth == 5:
        return
    
    temp_zone = copy.deepcopy(zone)

    
    moveUp()
    dfs(depth+1)
    zone = copy.deepcopy(temp_zone)
    
    moveDown()
    dfs(depth+1)
    zone = copy.deepcopy(temp_zone)

    moveLeft()
    dfs(depth+1)
    zone = copy.deepcopy(temp_zone)

    moveRight()
    dfs(depth+1)
    zone = copy.deepcopy(temp_zone)

dfs(0)

print(max_value)

이번 문제는 2048 게임의 조건대로 한번에 '상 하 좌 우' 중 한 방향으로 이동시킬 수 있다고 할 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 문제이다.

 

문제를 보자마자 '상하좌우로 블록을 이동시키는 함수(moveUp, moveDown, moveLeft, moveRight)'와 '현재 칸에서 가장 큰 블록을 찾는 함수(searchMaxValue)'를 구현해야겠다고 생각했고, 곧바로 구현에 들어갔다.

 

생각보다 문제의 조건이 까다롭긴 했지만 상하좌우로 블록을 이동시키는 함수을 구현하는 것은 크게 어렵지 않았지만, 다음과 같은 2가지 실수를 범했다.

 

1. 얕은 복사(shallow copy) 방식을 이용한 백트래킹

    # 얕은 복사 방식을 사용하여 이전 탐색에서 원래의 배열(temp_zone)이 변경된 상태로 다음 탐색을 하게됨
    
    temp_zone = copy.deepcopy(zone)
    
    moveUp()
    dfs(depth+1)
    zone = temp_zone
    
    moveDown()
    dfs(depth+1)
    zone = temp_zone

DFS를 사용해서 하나의  경로를 탐색한 후에, 다음 경로를 탐색하기 위해 2차원 리스트를 원상태로 복구시켜줄 때 temp_zone을 깊은 복사(deep copy)를 사용하지 않고 얕은 복사(shallow copy)를 해주어서 기존의 배열이 변경된 채로 다음 탐색을 이어가게 되어 올바르지 못한 결과가 나왔다.

 

    # 깊은 복사 방식 사용
    temp_zone = copy.deepcopy(zone)
    
    moveUp()
    dfs(depth+1)
    zone = copy.deepcopy(temp_zone)
    
    moveDown()
    dfs(depth+1)
    zone = copy.deepcopy(temp_zone)

따라서 깊은 복사방식(deep copy)를 사용하여 리스트를 완전히 복사하여 새로운 리스트를 만들어주고, 새로운 리스트를 다시 zone에 할당하여 원상복구된 상태로 나머지 경로를 탐색한 결과 올바르게 풀이할 수 있게 되었다. (Chat GPT 사랑해요) ⭐️⭐️

 

Q. 왜 copy 모듈로 깊은 복사를 해야 할까? 💡
A. 그 이유는 반복문에서 원본 그래프의 값을 바꾸기 때문에 백트래킹에서 원본 그래프를 보존하지 못하기 때문이다. 그래서 copy 모듈의 deepcopy 메서드로 복사해준다.

 

# 왼쪽으로 이동시키는 함수
def moveLeft(zone):
    zone = copy.deepcopy(zone)
    marged = [[False]*n for _ in range(n)]
    
    for i in range(n): # 행 
        for j in range(1,n): # 열
            if zone[i][j] == 0:
                continue
            for k in range(j-1,-1,-1):
                if zone[i][k] == zone[i][k+1] and not marged[i][k]:
                    zone[i][k] *= 2
                    zone[i][k+1] = 0
                    marged[i][k] = True
                    break
                elif zone[i][k] == 0:
                    zone[i][k] = zone[i][k+1]
                    zone[i][k+1]= 0 
                else:
                    break

    return zone

def dfs(depth,zone):

    searchMaxValue(zone)
    
    if depth == 5:
        return
    
    dfs(depth+1,moveUp(zone))
    dfs(depth+1,moveDown(zone))
    dfs(depth+1,moveLeft(zone))
    dfs(depth+1,moveRight(zone))

다른 사람의 풀이를 참고해본 결과, 본인과 같이 2차원 리스트를 전역으로 관리하는 방법도 있지만 위와 같이 '이동시키는 함수의 인자로 2차원 리스트를 전달받고, 그 내부에서 깊은 복사를 하여 변경한 리스트를 반환하는 방식'도 상당히 깔끔한 것 같다.(깊은 복사를 내부에서 해주면 원본에 영향을 주지 않음 !) 

 

전역으로 값을 관리하는 것보다 DFS의 인자로 원본 상태를 전달해주는 것이 더 안전하고 직관적인 것 같으니 이 방법도 자주 사용해야겠다.

 

2. else if 의 빈번한 사용

                for k in range(j+1,n):
                    if zone[i][k] == zone[i][k-1] and not marged[i][k]:
                        zone[i][k] *= 2
                        zone[i][k-1] = 0
                        marged[i][k] = True
                        break
                    elif zone[i][k] == zone[i][k-1] and marged[i][k]:
                        break
                    elif zone[i][k] == 0:
                        zone[i][k] = zone[i][k-1]
                        zone[i][k-1] = 0
                    elif zone[i][k] != 0 and zone[i][k-1] != zone[i][k]: # elif 지옥 ..
                        break

이전에 풀이에서 자꾸 60%에서 오답이 나와 어떤 부분에서 문제가 발생했는지 계속 고민해본 결과, 블록을 이동시키는 함수 내에 오류가 있다는 점을 인지할 수 있었다.

 

그래서 조건문을 확인해보니 조건이 명확하지 않은 elif문이 빈번하게 사용되고 있었음을 알 수 있었다.

    for i in range(n): # 행 
        for j in range(1,n): # 열
            if zone[i][j] == 0:
                continue
            for k in range(j-1,-1,-1):
                if zone[i][k] == zone[i][k+1] and not marged[i][k]:
                    zone[i][k] *= 2
                    zone[i][k+1] = 0
                    marged[i][k] = True
                    break
                elif zone[i][k] == 0:
                    zone[i][k] = zone[i][k+1]
                    zone[i][k+1]= 0 
                else: # 확실하게 처리해야 하는 조건까지만 if/elif로 처리하고 나머지는 모두 else로 처리
                    break

따라서 elif가 아닌, 확실한 조건을 제외한 나머지는 모두 else로 분기처리하여 오류를 잡을 수 있었다. 다음부터 이러한 구현이나 시뮬레이션 문제에서는 elif의 빈번한 사용을 지양할 할 예정이다. (하나의 오류가 큰 오류를 범할 수 있기에)

 

구현과 시뮬레이션, 완전탐색과 원 상태로 복구시켜주는 백트래킹을 한번에 복습할 수 있었고, 문제를 풀이할 때 범할 수 있는 실수를 찾게 된 좋은 문제였다 :)