[Debugging] - 내 코드는 왜 스파게티가 되었는가? by 2048(Easy) (BOJ 12100)

• 이번 글은 BOJ #12100, 2048(Easy) 문제를 풀며 디버깅 한 과정을 담고 있습니다. 문제 명세 및 입출력 예시는 링크를 참고해주세요!

디버깅?

이번 포스팅은 알고리즘 카테고리로 넣어도 무관한 내용이긴 한데요, 알고리즘에 대한 접근 방식 보다는 문제를 푸는 과정에서 했던 디버깅 과정에 중점을 두고자 디버깅 카테고리로 분류하여 작성하려 합니다.

디버깅(Debugging) : 말 그대로 프로그램 상에 존재하는 여러 오류(bug)들을 제거(de) 한다는 의미를 가지고 있습니다.

일반적으로 개발 과정에 있는 소프트웨어, 컴퓨터 프로그램 속 오류를 찾는 의미로 사용되는 말이지만, 알고리즘 문제를 푸는 과정에서도 꼭 필요한 것이 디버깅이라고 생각됩니다. 알고리즘 자체는 간단하더라도 구현의 복잡도가 올라갈수록 어디에서 에러가 발생했는지 확인하기 쉽지 않아지기 때문입니다.

접근 방식

• 특정 알고리즘 접근 방식 보단, 2048 게임의 룰을 어떤 식으로 코드로 잘 옮길 것 인지에 중점을 두어 진행했습니다.
• 상, 하, 좌, 우의 네 방향으로 이동할 수 있다는 점과 최대 5번의 이동이 가능하다는 점을 고려하여, itertools 라이브러리의 product 를 활용하여 네 가지 방향 중 5개를 중복 선택하여 만들 수 있는 모든 경우의 수를 구했습니다. 이 경우의 수들을 모두 순회하며 가능한 최대의 블록 값을 얻어 올 수 있도록 구현했습니다.

첫 번째 시도

• 우선, 상,하,좌,우 방향으로의 모든 이동에 대해 코드를 구현했습니다.

# BOJ 12100, 2048(Easy)
import sys, copy
from itertools import product
N_INF = int(1e9) * -1
input = sys.stdin.readline

def move_map(arr, direct, n):

    if direct == 1: # 위쪽으로 이동
        # 모든 열을 순회하며 최상단 행으로 끌어올림
        for i in range(n):
            # 해당 열의 모든 행을 돌며 최대한 위로 올림 (0번째 행은 가장 위쪽이라 고려 x)
            success_sum = False
            for j in range(1, n):

                # 해당 숫자가 0이라면 확인할 필요없음
                if arr[j][i] == 0:
                    success_sum = False
                    continue

                # 해당 숫자 저장 후 해당 자리에는 0을 세팅
                target = arr[j][i]
                arr[j][i] = 0


                # 바로 위에 다른 숫자가 있을 때까지 찾음
                j -= 1
                while j >= 0:
                    if arr[j][i] != 0:
                        break
                    j -= 1

                # 만약 위에가 없어서 j가 -1이 되었다면, 가장 위에 해당 숫자를 올림
                if j == -1:
                    arr[0][i] = target
                    success_sum = False
                    continue

                # 만약 위에 다른 숫자가 있다면, 해당 숫자와 같은지 확인
                if arr[j][i] == target and not success_sum:
                    arr[j][i] = target * 2
                    success_sum = True
                # 같지 않다면, 바로 직전 자리에 배치
                else:
                    arr[j+1][i] = target
                    success_sum = False

    elif direct == 2:  # 오른쪽으로 이동
        # ... (중략)

        
n = int(input().rstrip())
arr = []
for _ in range(n):
    row_data = list(map(int, input().rstrip().split()))
    arr.append(row_data)

steps = [1, 2, 3, 4] # 위, 오른쪽, 아래, 왼쪽
step_comb = list(product(steps, repeat=5))

max_val = N_INF
# 모든 이동 조합의 경우의 수를 순회
for step in step_comb:

    # 기존의 맵을 카피하여 수행
    copy_map = copy.deepcopy(arr)

    # step 속 다섯번의 이동을 순차적으로 순회
    for s in step:
        move_map(copy_map, s, n)

    # 이동 후, 블록의 최댓값을 구함
    for row in copy_map:
        tg = max(row)
        if tg > max_val:
            max_val = tg

print(max_val)

• 이차원 리스트를 활용하다보니, 각 방향에 대해 이동하는 과정에서 열과 행, 그리고 고려되는 각 순번들이 바뀌었습니다. 그래서 처음에는 이 모든 방향에 대해서 각각 분기하여 구현을 진행했습니다.

스파게티 코드

• 위의 코드와 같이 첫 번째 시도에서 거의 200줄에 가까운 코드가 나왔습니다. 코드 자체가 길어지니 문제를 디버깅 하는 과정에서 어느 부분에 에러가 났는지 확인하기가 매우 어려웠습니다. 흔히 말하는 스파게티 코드와 같은 형태가 되었습니다.

  스파게티 코드 : 프로그램의 소스 코드가 복잡하게 얽힌 모습을 스파게티 면발에 비유한 표현입니다. (출처 - Wikipedia)

• 예를 들어 이동하는 과정에서 어떤 셀이 다른 위치로 이동했다면 그 자리의 값을 0으로 바꿔줘야 하는데, 그 부분을 놓쳐 수정해야 했습니다. 그러나 수정하는 과정에서 네 개의 서로 다른 분기에 대해 모두 수정을 진행해줘야 했습니다.

• 또한 다른 문제가 발생했을 때도 각 네 개의 분기에 대해 수정을 진행해줘야 했기 때문에 이 과정에서 실수가 발생할 확률이 매우 높다고 느껴졌습니다.

리팩토링

• 알고리즘 문제를 푸는 과정의 코드지만, 그래도 문제를 제대로 풀고 에러를 잡기 위해선 리팩토링이 필요하다고 생각했습니다. 이동하는 과정의 코드를 하나로 합칠 수 있는 방안에 대해서 고민했습니다.

• 위의 코드를 기준으로, ‘상’ 방향으로 이동하는 코드만 남겼습니다. 그리고, 나머지 ‘하’, ‘좌’, ‘우’의 이동에 대해서는 맵 전체를 회전한 뒤 이동하는 방식으로 구현했습니다. 예를 들어 ‘좌’ 방향으로 이동하는 코드는, 맵 전체를 오른쪽으로 회전한 뒤, ‘상’ 방향을 기준으로 이동을 수행하고, 다시 맵 전체를 왼쪽으로 회전하는 방식으로 진행했습니다.

• 이를 바탕으로 구현한 코드는 아래와 같습니다.

# BOJ 12100, 2048(Easy)
import sys, copy
from itertools import product
N_INF = int(1e9) * -1
input = sys.stdin.readline

def rotate_map(arr, direct, n):
    new_map = copy.deepcopy(arr)

    if direct == 2:
        # 오른쪽 방향으로 회전
        for i in range(n):
            for j in range(n):
                new_map[j][n-1-i] = arr[i][j]
    elif direct == 4:
        # 왼쪽 방향으로 회전
        for i in range(n):
            for j in range(n):
                new_map[n-1-j][i] = arr[i][j]

    return new_map


def move_map(arr, n):
    # 모든 열을 순회하며 최상단 행으로 끌어올림
    for i in range(n):
        # 해당 열의 모든 행을 돌며 최대한 위로 올림 (0번째 행은 가장 위쪽이라 고려 x)
        success_sum = False
        for j in range(1, n):
            # 해당 숫자가 0이라면 확인할 필요없음
            if arr[j][i] == 0:
                success_sum = False
                continue

            # 해당 숫자 저장 후 해당 자리에는 0을 세팅
            target = arr[j][i]
            arr[j][i] = 0


            # 바로 위에 다른 숫자가 있을 때까지 찾음
            j -= 1
            while j >= 0:
                if arr[j][i] != 0:
                    break
                j -= 1

            # 만약 위에가 없어서 j가 -1이 되었다면, 가장 위에 해당 숫자를 올림(success_sum은 그대로)
            if j == -1:
                arr[0][i] = target
                continue

            # 만약 위에 다른 숫자가 있다면, 해당 숫자와 같은지, 그리고 연속되어 합쳐지는 것은 아닌지 확인
            if arr[j][i] == target and not success_sum:
                arr[j][i] = target * 2
                success_sum = True
            # 같지 않다면, 바로 직전 자리에 배치
            else:
                arr[j+1][i] = target
                success_sum = False


n = int(input().rstrip())
arr = []
for _ in range(n):
    row_data = list(map(int, input().rstrip().split()))
    arr.append(row_data)

steps = [1, 2, 3, 4] # 위, 오른쪽, 아래, 왼쪽
step_comb = list(product(steps, repeat=5))


max_val = N_INF
# 모든 이동 조합의 경우의 수를 순회
for step in step_comb:

    # 기존의 맵을 카피하여 수행
    copy_map = copy.deepcopy(arr)

    # step 속 다섯번의 이동을 순차적으로 순회
    for s in step:
        if s == 2:
            copy_map = rotate_map(copy_map, 4, n)
            move_map(copy_map, n)
            copy_map = rotate_map(copy_map, 2, n) # 원상복구
        elif s == 4:
            copy_map = rotate_map(copy_map, 2, n)
            move_map(copy_map, n)
            copy_map = rotate_map(copy_map, 4, n) # 원상복구
        elif s == 3:
            copy_map = rotate_map(copy_map, 2, n)
            copy_map = rotate_map(copy_map, 2, n)
            move_map(copy_map, n)
            copy_map = rotate_map(copy_map, 2, n) # 원상복구
            copy_map = rotate_map(copy_map, 2, n) # 원상복구
        else:
            move_map(copy_map, n)

    # 이동 후, 블록의 최댓값을 구함
    for row in copy_map:
        tg = max(row)
        if tg > max_val:
            max_val = tg

print(max_val)

• 위와 같이 rotate_map 함수를 추가로 구현해 오른쪽, 왼쪽으로 맵을 회전시킬 수 있도록 했습니다.
• 이와 같이 코드를 리팩토링 하니, 확실히 맵을 이동하는 과정에 있어서 디버깅이 훨씬 수월하다는 느낌을 받았습니다. (물론 여전히 복잡한 느낌이 없지 않아 있는 것 같습니다)

Debugging

• 이제 코드가 조금 간결해졌으니, 본격적으로 디버깅을 수행했습니다. 코드를 한 줄 한 줄 따라가면서 의도한대로 코드가 수행되고 있는지 파악했습니다.

• 얼마 안되어 아래의 버그를 발견했습니다.

  # 해당 숫자가 0이라면 확인할 필요없음
  if arr[j][i] == 0:
      success_sum = False
      continue
  

  • success_sum은 이미 한 번 합쳐진 블록이 해당 이동에서 추가로 합쳐지는 것을 방지하기 위한 일종의 flag 변수인데요, 해당하는 항의 숫자가 0일 때에 이 변수를 False로 초기화해주고 있었습니다.
  • 그러나 따져보면 해당 위치의 숫자가 0일 때는 success_sum을 False로 바꿔주면 안됩니다. 0의 경우에는 해당 위치보다 위에 있는 숫자와 합치는 과정에 영향을 미치지 않기 때문에, success_sum 변수를 기존대로 유지해줘야 합니다.

• 처음 스파게티였던 코드에서는 이러한 디버깅이 매우 어렵게 느껴졌는데, 코드가 간결해지고 분기의 선택지가 줄어드니 확실히 조금 더 편하게 디버깅을 수행할 수 있었던 것 같습니다.

최종 구현

# BOJ 12100, 2048(Easy)
import sys, copy
from itertools import product
N_INF = int(1e9) * -1
input = sys.stdin.readline

def rotate_map(arr, direct, n):
    new_map = copy.deepcopy(arr)

    if direct == 2:
        # 오른쪽 방향으로 회전
        for i in range(n):
            for j in range(n):
                new_map[j][n-1-i] = arr[i][j]
    elif direct == 4:
        # 왼쪽 방향으로 회전
        for i in range(n):
            for j in range(n):
                new_map[n-1-j][i] = arr[i][j]

    return new_map

def move_map(arr, n):
    # 모든 열을 순회하며 최상단 행으로 끌어올림
    for i in range(n):
        # 해당 열의 모든 행을 돌며 최대한 위로 올림 (0번째 행은 가장 위쪽이라 고려 x)
        success_sum = False
        for j in range(1, n):
            # 해당 숫자가 0이라면 확인할 필요없음
            if arr[j][i] == 0:
                continue

            # 해당 숫자 저장 후 해당 자리에는 0을 세팅
            target = arr[j][i]
            arr[j][i] = 0

            # 바로 위에 다른 숫자가 있을 때까지 찾음
            j -= 1
            while j >= 0:
                if arr[j][i] != 0:
                    break
                j -= 1

            # 만약 위에가 없어서 j가 -1이 되었다면, 가장 위에 해당 숫자를 올림(success_sum은 그대로)
            if j == -1:
                arr[0][i] = target
                continue

            # 만약 위에 다른 숫자가 있다면, 해당 숫자와 같은지, 그리고 연속되어 합쳐지는 것은 아닌지 확인
            if arr[j][i] == target and not success_sum:
                arr[j][i] = target * 2
                success_sum = True
            # 같지 않다면, 바로 직전 자리에 배치
            else:
                arr[j+1][i] = target
                success_sum = False


n = int(input().rstrip())
arr = []
for _ in range(n):
    row_data = list(map(int, input().rstrip().split()))
    arr.append(row_data)

steps = [1, 2, 3, 4] # 위, 오른쪽, 아래, 왼쪽
step_comb = list(product(steps, repeat=5))

max_val = N_INF
# 모든 이동 조합의 경우의 수를 순회
for step in step_comb:

    # 기존의 맵을 카피하여 수행
    copy_map = copy.deepcopy(arr)

    # step 속 다섯번의 이동을 순차적으로 순회
    for s in step:
        if s == 2:
            copy_map = rotate_map(copy_map, 4, n)
            move_map(copy_map, n)
            copy_map = rotate_map(copy_map, 2, n) # 원상복구
        elif s == 4:
            copy_map = rotate_map(copy_map, 2, n)
            move_map(copy_map, n)
            copy_map = rotate_map(copy_map, 4, n)  # 원상복구
        elif s == 3:
            copy_map = rotate_map(copy_map, 2, n)
            copy_map = rotate_map(copy_map, 2, n)
            move_map(copy_map, n)
            copy_map = rotate_map(copy_map, 2, n) # 원상복구
            copy_map = rotate_map(copy_map, 2, n) # 원상복구
        else:
            move_map(copy_map, n)

    # 이동 후, 블록의 최댓값을 구함
    for row in copy_map:
        tg = max(row)
        if tg > max_val:
            max_val = tg

print(max_val)

Lesson

아마 위의 코드보다 더 간결하고 가독성이 높은 코드가 많을 것이라고 생각합니다. 그럼에도 처음에 구현했던 코드보다 더 간결한 코드를 만드는 과정에서 조금 더 코드 한 줄 한 줄의 의미에 대해서 고민해봤던 것 같아 좋은 경험이었습니다. 앞으로 알고리즘 문제를 푸는 과정에서 코드의 가독성과 복잡성을 줄일 수 있는 방향으로 더 많이 고민해봐야 될 것 같습니다.