[DFS & DP] BJ_1937, 욕심쟁이 판다

[문제의 접근] 

 500 X 500의 배열이 주어지고, 동서남북으로 이동이 가능하다. 당신이 제일 먼저 생각하게 되는 풀이법은? 

 바로 BFS일 것이다. 그런데 이 문제는 잘 읽어보게 되면, 시작하는 위치와 더불어 방문의 순서가 매우 중요하다는 것을 깨달을 수 있다. 간단한 예시로 아래의 배열을 보자. 가장 작은 대나무의 위치인 5에서 시작한다고 가정했을 때 DFS로 탐색하는 경우는 한번에 한 위치만 방문하기 때문에 위와 같이 최대거리 4를 찾아낼 수 있지만, BFS로 탐색할 경우 최대 거리를 3밖에 찾을 수 없다. 거리 4를 도출하기 위해서는 한번 방문한 위치를 다시 방문해야 하고, 이는 가장 기본적인 BFS탐색 원리를 위배하는 일이다. 

 

 즉, 이문제는 DFS로 풀어야 하는 문제다. 보통 DFS로 풀기 위한 배열의 범위는 10 내외이다. 모든 경우를 탐색하는 경우 10! 계산량이 나오고 이를 계산하면 약 3600만이 나온다. 그럼 1초의 연산량 1억보다는 작지만, 세부 연산이 더해지면 time limit에 걸릴 수 있기 때문에, 쉽게 풀수 있는 문제는 범위 9이하로 주어진다. 그럼 범위 500은? DFS로만은 절대 풀 수 없다. 그럼 어떻게 해야할까? Dynamic Programming의 힘을 빌려야 하는 문제다.

 

[Dynamic Programming의 장점]

 Dynamic Programming을 이용하면 특정 위치 상태에서의 최적값을 구한 배열을 참조하여 다음해를 빠르게 구할 수 있기 때문에(가지치기와 유사) 배열이 꽤 크더라도 빠른 속도로 계산을 해 나갈 수 있다. dynamic programming의 경우 경우의 수를 구하는 문제는 상당히 복잡하다. 

 

 Dynamic Programming을 푸는 방법에는 크게 두가지 접근법이 존재한다. 바로 Top-down과 bottom-up이다. 보통의 경우에는 dynamic programming을 위한 점화식을 찾아낼 수 있다면 Top-down approach가 훨씬 쉬운 방법이며, 그렇지 않다면 Bottom-up approach를 생각해 보게 된다. 

 

[Top-down Approach]

 많은 경우, 점화식으로 주어지는 Top-down Approach는 DFS와 유사하게 재귀적으로 이루어진다. 이 문제의 경우 점화식은 아래와 같다. 즉 현재 위치에서의 최적값은 현재 위치에서 이동할 수 있는 새로운 위치에서의 최적값에 1을 더한 값과 현재 값 사이의 최대값이다. 문제의 접근이 쉬운 반면에, 재귀적인 계산이 메모리 효율적이지는 않다. 

dp[y][x] = max(dp[y][x], dp[new_y][new_x] + 1)

 아래 코드를 보면서 이해해 보자. Python과 C++의 접근에 큰 차이는 없다. 기본적으로 이미 방문한 적이 있는 위치는 최적값이 계산된 상태이므로 그대로 값을 return하여 이용하면 되고, 그렇지 않은 경우 1로 초기화 하여 4방향을 탐색해서 현재의 위치보다 대나무 갯수가 많은 위치만을 재귀적으로 탐색하여 max값은 도출해 주면 되는 형식이다. 

 

<Python>

def go(i, j):
    if d[i][j] != 0: # 이미 방문한 값은 최적값이므로 그대로 반영
        return d[i][j]
    d[i][j] = 1 # 시작한 위치 자체도 1개로 포함되므로, 최소값은 1이다.
    for k in range(4):
        y, x = i +dy[k], j+dx[k]
        if 0 <= x < n and 0 <= y < n:
            if a[i][j] < a[y][x]: # 대나무 개수가 많아야 진행
                d[i][j] = max(d[i][j], go(y, x) + 1)
    return d[i][j]

 

<C++>

int dfs(int r, int c) {
    if (dp[r][c] != -1) return dp[r][c];
    int &ans = dp[r][c];
    ans = 1;

    for (int i=0; i<4; i++) {
        int nr = r+dy[i];
        int nc = c+dx[i];

        if ((nr < 0) || (nr >= n) || (nc < 0) || (nc >= n)) continue;
        if (arr[nr][nc] > arr[r][c]) {
            ans = max(ans, dfs(nr, nc) + 1);
        }
    }
    return ans;
}

 

[Bottom-up Approach]

 보통의 bottom-up의 경우는 재귀적으로 함수가 구성되지 않고 제일 하위의 계산을 먼저 수행한 후에 그 결과를 바탕으로 상위의 결과를 도출하는 식이다. for문으로 탐색하기 때문에 계산량 계산이 쉽고 직관적으로 계산이 가능하지만, 제일 하위가 어떤 문제인지를 파악해야 하며 순차적으로 계산을 디자인 해야 하기 때문에 어려운 점이 있다. 

 이 문제의 경우는 팬더는 대나무가 작은 곳에서 많은 곳으로 이동할 수 밖에 없기 때문에 대나무가 가장 많은 곳이 바로 하위 계산의 시작점이라고 볼수 있다. dp배열의 방문하지 않은 지점은 현재 위치보다 대나무의 갯수가 적거나 같은 지점이므로 계산이 무의미하기 때문에 이를 바탕으로 대나무의 갯수가 많은 곳에서 적은곳으로 이동하며 계산을 진행하면 된다. 

 그러기 위해서는 배열의 y, x, 좌표와 대나무의 갯수를 묶어서 tuple로 만들고 대나무의 갯수가 가장 많은 곳에서 낮은 순으로 정렬하여 계산하다. 아래 코드를 보면 이해가 될 것이다. 

 

<Python>

b = []

for i in range(n):
    for j in range(n):
        b.append((i,j,a[i][j]))

b.sort(key=lambda val: -val[2])

# 팬더는 대나무가 작은 곳에서 많은 곳으로 이동할 수 밖에 없다. 
# 그렇다면 array value가 가장 큰곳(대나무가 가장 많은 곳)에서 부터 시작해서 대나무가 적은 곳으로 for문을 돌린다면,
# 0인 곳은 어차피 현재 위치보다 대나무가 적거나 같다는 뜻이 되므로, 이동할 수 없음을 의미하므로 Logic이 성립한다. 
# 만약 문제가 대나무가 같은 곳으로도 이동할 수 있었다면, 대나무가 같은 곳 끼리의 우선순위가 문제가 될 수 있겠다.
# 예시
# 1 3 2
# 4 3 4 
# 6 4 5
for y, x, val in b:
    d[y][x] = 1
    for k in range(4):
        ny, nx = y+dy[k], x+dx[k]
        if 0 <= ny < n and 0 <= nx < n:
            if a[y][x] < a[ny][nx]:
                d[y][x] = max(d[y][x], d[ny][nx] +1)

이 Bottom-up approach의 경우는 문제가 대나무가 적은 곳에서 많은 곳으로 이동하는 경우이기에 성립하는 것이며, 만약에 크거나 같은 곳으로 이동할 수 있다면 위의 풀이는 성립하지 않는다. 아래 예시에서와 같이 대나무의 수가 같은 위치의 우선 순위에 따라서 결과가 바뀌기 때문이다. 이 때는 우선순위에 대해서 따로 계산해 줘야 할 것이다. 

최종해는 dp 배열에서 최대값을 찾아주면 끝난다. 아래 솔루션의 결과를 주목해 보자. C++의 경우는 Python 대비 풀이 시간과 메모리 사용량이 압도적으로 작다. Python으로 풀이한 Top-down과 Bottom-up의 경우는 계산 시간에는 큰 차이가 없지만, 재귀적으로 접근하지 않은 Bottom-up approach가 절반에 가까운 메모리 절약을 보인다. 

 

<C++ 풀이>  https://github.com/Koo82/Algotirhm/blob/main/%5BDP%5DBJ_1937.cpp

GitHub - Koo82/Algotirhm

<Python 풀이> https://github.com/Koo82/Algotirhm/blob/main/%5BDP%5DBJ_1937.py

GitHub - Koo82/Algotirhm