[ Python ] BOJ // Q12100 - 2048 DFS 알고리즘 사용 코드리뷰

백준온라인저지 BOJ Question 12100 - 2048 (EASY)

많은 사람들이 경험해 보았을 것이다. 수학을 공부하다 보면, 분명 기본 공식은 너무 쉬운데 그것을 활용하는 것이 참 어렵다. 나는 수학을 "공부" 한다는 것이 곧 그러한 문제들을 어떻게 유연하게 대처하는지, 어떻게 그 필요한 공식을 떠올리는지에 대한 훈련이라고 생각한다. 또 다르게 말하자면 뇌를 말랑말랑하게 유지시키는 게 아닐까 싶다. 나에겐 코딩이 특히나 그 말랑말랑한 사고를 강제하기에 더욱더 흥미가 생겼었다.나는 이미 이 블로그에도 글을 썼지만, DFS 알고리즘에 대해서 이해는 하고있다. 하지만 정작 틀에서 조금 벗어난 문제에서 DFS를 직접 활용해보려니 상당히 막막함을 경험했고, 물론 결국은 풀어냈다. 나름의 기념비적인 문제이기에 나의 공부를 기록하기 위해, 그리고 해당 문제 때문에 혹시나 찾아왔을 다른 방문자를 위해 나의 코드를 나누고자 한다.

Given ) N*N 크기의 게임판에 2048 게임이 진행된다. 블록은 무조건 2의 제곱꼴이며 0은 빈칸을 나타낸다.
게임은 2048의 룰을 따른다. 다만, 실제 게임에서는 매 움직임마다 랜덤 블록이 추가되나, 그것은 제외한다.
Input ) 첫째 줄에 게임판의 크기 N 이 주어지고 그 다음 줄부터 N 줄에 걸쳐 게임판의 초기 상태가 주어진다.
( 1 <= N <= 20 )

Output) 5번 이동시켜서 얻을 수 있는 최대 블록크기를 출력하라

Approach ) 각 방향으로 움직이는 이동 함수를 작성하고 해당 함수들을 DFS 로 순회시켜서 MAX 값을 받아내자

문제를 보고나서 나의 첫 접근방법 유추는 위와 같았다. 하지만 지금 다시 생각을 해보니 무조건적으로 모든 경우의 수를 일단 탐색을 해봐야 최댓값을 구할 수 있으므로 DFS 대신 BFS 알고리즘을 선택해도 문제를 푸는 데는 이상이 없을 듯하다.

def move_right(data):
    lst = []
    ck = False
    for i in range(n):
        h_count = 1
        lst = [j for j in data[i] if j >0]
        m = len(lst)
        for j in range(1,m+1): #[2,2,2]
            if j != m:
                if ck:
                    ck = False
                    continue
                if lst[-j] != lst[-j-1]:
                    data[i][-h_count] = lst[-j]
                    h_count+=1
                    continue
                elif lst[-j] == lst[-j-1]:
                    data[i][-h_count] = lst[-j]*2
                    ck = True
                    h_count+=1
            else:
                if ck:
                    ck=False
                    data[i][-h_count] = 0
                    continue
                else:
                    data[i][-h_count] = lst[-j]
        if n!=h_count:
            while True:
                h_count+=1
                data[i][-h_count] = 0
                if n == h_count:
                    break
        lst = []
    return data

움직임을 구현하기 위해 내가 생각한 필요 요소들은 다음과 같았다.

각 행의 0을 제외한 모든 요소를 찾는다.
1을 통해 얻은 요소들을 순서에 맞게 순회하며 합쳐질 수 있는지 확인한다.
합쳐진다면 합쳐진 값을, 합쳐지지 않는다면 그대로의 값을 조건에 맞춰서 return 테이블에 삽입한다.
4를 통해 모두 삽입하고도 테이블이 빈다면 남은 빈칸을 모두 0으로 채운다.

우선 move 함수에는 무조건 현재 테이블 data 만 변수로 받도록 설정했다. DFS 알고리즘의 Depth가 깊어짐에 따라 매번 다른 데이터 테이블이 주어질 것이므로 data 값이 변수로 삽입되는 것은 당연하다. move함수 내에 count(이동 횟수)를 필터링하는 코드를 짜보기도 했지만, 어차피 DFS 함수 내에서 count를 제어하면 되므로 굳이 move함수 안에 count변수를 넣는 건 복잡하기만 하다고 판단했다.

함수 내에서 0이 아닌 지역변수 lst를 생성했다. 그 이유는 2048의 룰 특성상 0은 다음 움직임에 전혀 영향을 주지 못하고, 0을 제외한 숫자들의 배열에 따라 return 테이블이 결정되기 때문이다. 따라서 (1) 리스트 컴프리헨션을 통해 현재 행에서 0 이상인 값의 지역변수 lst 리스트를 생성했고 그 (2), (3) 리스트의 값을 순회하여 같은 값이 반복되면 합쳐지는 것으로 판단하여 오른쪽으로 스와이프 할 때의 함수이므로, return 테이블의 (2), (3) 오른쪽부터 채워주도록 코딩(-h_count)했다. 그리고 lst의 마지막 인덱스의 경우 만약 그 바로 전 인덱스와 합쳐지지 않는다면 더 이상 합칠 수 있는 숫자가 없으므로, 그 숫자 그대로 h_count인덱스에 추가해주었다.
마지막으로 (4) 모든 lst를 채워 넣었다면 모든 숫자가 이동했고 남은 자리는 모두 0 이기 때문에 n과 현재 h_count를 비교하여 남은 자리를 모두 0으로 채워 넣고, 현재 바뀐 테이블을 return 해주었다.

왼쪽으로 스와이프 할 때의 move_left 함수는 숫자를 채워넣는 방향만 반대로 바뀌기때문에 따로 작성하진 않겠다.

def move_up(data):
    lst = []
    ck = False
    for i in range(n):
        v_count = 0
        lst = [ j[i] for j in data[0:n] if j[i] > 0]
        m = len(lst)
        for j in range(m):
            if j != m-1:
                if ck:
                    ck = False
                    continue
                if lst[j] != lst[j+1]:
                    data[v_count][i] = lst[j]
                    v_count+=1
                    continue
                elif lst[j] == lst[j+1]:
                    data[v_count][i] = lst[j]*2
                    ck = True
                    v_count+=1
            else:
                if ck:
                    ck=False
                    data[v_count][i] = 0
                    continue
                else:
                    data[v_count][i] = lst[j]
        if n-1!=v_count:
            while True:
                v_count+=1
                data[v_count][i] = 0
                if n-1 == v_count:
                    break
        lst = []
    return data

위로 스와이프 할 때 또한 오른쪽으로 스와이프 할 때 필요했던 구현 요소는 비슷했다. 하지만 추가로 2차원 리스트는 각 row별로 묶여있지만 위로 스와이프할 땐 같은 column의 값이 필요하므로 모든 row의 같은 인덱스 값을 가져와서 column 데이터로 사용해야 했다. 그래서 앞선 가로 스와이프 코드와 가장 큰 차이점을 보이는 것이 바로 lst 부분이다. 리스트 컴프리헨션을 마찬가지로 사용하되, 모든 행의 i 인덱스만을 가져오고 만약 0 이상이라면 사용하는 방식이다.

ans = 0

def dfs(data,count):
    global ans
    if count >= 5:
        for i in range(n):
            for j in range(n):
                ans = max(ans,data[i][j])
        return
    dfs(move_right([i[:] for i in data]),count +1)
    dfs(move_left([i[:] for i in data]),count +1)
    dfs(move_down([i[:] for i in data]),count +1)
    dfs(move_up([i[:] for i in data]),count +1)

dfs(TABLE,COUNT)
print(ans)

마지막으로 내가 가장 애를 먹었던 DFS 구현부이다. 우선 정리하자면, DFS 구현을 위해 필요한 요소는 다음과 같다.

Depth 가 5 일 때 현재 테이블 내 요소의 최대 크기 찾고 ans 값과 비교하여 더 큰 값을 저장하기.
각 Depth 마다 상/하/좌/우 스와이프를 각각 수행하고 Depth 값을 증가시킬 것.
2를 수행하며 같은 Depth의 각 스와이프가 다른 스와이프에 영향을 주지 않을 것.

(1)과 (2)는 사실 그렇게 어렵지 않았다. 하지만 계속해서 시도를 해도 (3)의 원본 테이블에 영향이 가서 정확한 값의 도출이 불가능했다. 하지만 해결방법은 그다지 어렵지 않은 방법으로 재귀 DFS의 변수 테이블에 현재 테이블 슬라이싱 해서 복사하여 넣어주는 방법으로 해결할 수 있었다.

deepcopy 라이브러리를 사용하는 것보다는 이와 같이 슬라이싱을 통한 리스트 복사가 더욱 효과적이라는 것을 알고 있었기에 더 빨리 해결할 수 있었다.

[[ 마무리 ]]
개발직군 면접에서는 자신의 코드에 대한 리뷰 또한 질문한다고 한다. 자신이 문제 해결을 위해 그 코드를 직접 작성했더라도 그것을 구동시키는 과정과 그 코드에 대해서 남에게 해설해내는 부분은 비슷하지만 동시에 크게 다른 부분이라고 생각한다. 수학 문제도 자신이 풀 때 한 번, 그것을 남에게 설명하기 위해 다시 고민할 때 두 번 공부되듯이 코드 또한 남에게 나의 코드를 설명하는 그 행위 자체로 다시 한번 공부가 된다고 생각한다. 또한 그 문제의 해결을 위해 무엇을 구현하고자 했고, 무엇에 막혔으며, 무엇을 통해 해결했는지는 문제를 푸는 당시의 자신은 알겠지만 그것은 시간이 지나면 잊혀진다. 지금까지 적다면 적고 많다면 많은 알고리즘 문제들을 접해봤지만, 이 글로서 코드 리뷰의 첫걸음을 떼고자 한다.