다이나믹 프로그래밍 - 금광

금광 (Python)

📝 문제 설명

n x m 크기의 금광이 있습니다.
금광은 1 x 1 크기의 칸으로 나누어져 있으며 각 칸은 특정한 크기의 금이 들어 있습니다.
채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다.
맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다.
이후에 m - 1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의
위치로 이동해야 합니다.
결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력 하는 프로그램을 작성하세요.

---

📌 조건

• 입력 조건

  • 첫째 줄에 테스트 케이스 T가 입력됩니다. (1 <= T <= 1,000)
    • 각 테스트 케이스는 줄 바꿈을 이용해 구분합니다
  • 매 테스트 케이스 첫째 줄에 n과 m 이 공백으로 구분되어 입력됩니다
    • (1 <= n, m <= 20)
  • 둘째 줄에 n x m개의 취에 매장된 금의 개수가 공백으로 구분되어 입력됩니다.
    • (1 <= 각 위치에 매장된 금의 개수 <= 100)

• 출력 조건

  • 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력합니다..

---

🔽 입력 예시

2
3 4
1 3 3 2 2 1 4 1 0 6 4 7
4 4
1 3 1 5 2 2 4 1 5 0 2 3 0 6 1 2

🔼 출력 예시

19
16

---

💡 문제 해결 접근

1. 매번 오른쪽 위, 오른쪽, 오른쪽 아래 로 이동 한다고 하니 이동 방향을 설정해서 이동할 수 있는 경우의 수에서 최댓값을 가지는 경우로 갱신해줘야 한다.

def solution_bfs(n, m, graph):
    from collections import deque
    step = [[0,1], [1,1], [-1,1]]
    result = 0
    for i in range(n):
        start = [i,0]
        queue = deque([start + [graph[i][0]]])
        while queue:
            x, y, total = queue.popleft()
            for j in range(len(step)):
                nx = x + step[j][0]
                ny = y + step[j][1]
                if nx < 0 or nx > n-1 or ny < 0 or ny > m - 1:
                    continue
                n_total = total + graph[nx][ny]
                queue.append([nx, ny, n_total])
                result = max(n_total,result)
    return result

---

🏆 정답 코드

def 모범답안(n, m, dp):
    for j in range(1, m):
        for i in range(n):
            if i == 0: left_up = 0
            else: left_up = dp[i-1][j-1]
            if i == n - 1: left_down = 0
            else: left_down = dp[i+1][j-1]
            left = dp[i][j-1]
            dp[i][j] = dp[i][j] + max(left_up, left_down, left)
    result = 0
    for i in range(n):
        result = max(result, dp[i][m-1])
    return result

---

🔥 느낀 점

• 내 풀이는 bfs 방식에 최댓값을 갱신 하는 방법으로 dp 보다 비효율적인 탐색이 더 들어가서 dp 로 구현해야 한다 😭
• BFS vs DP 방식 비교

비교 항목	BFS 방식	모범 답안 (DP 방식)
알고리즘 유형	너비 우선 탐색 (BFS)	동적 계획법 (DP)
탐색 방식	큐(Deque)를 사용해 모든 가능한 경로 탐색	이전 결과를 활용하여 최적해만 계산
시간 복잡도	(O(3^m)) (경우의 수 많음)	(O(n \cdot m)) (효율적)
공간 복잡도	(O(n \cdot m)) (큐에 경로 저장)	(O(n \cdot m)) (DP 테이블)
장점	- 최적 경로를 찾을 수 있음 - DFS보다 안정적인 탐색	- 가장 빠르고 효율적 - 불필요한 탐색 없이 최적해를 구함
단점	- 경우의 수가 많아 연산량이 큼 - 큐에 많은 데이터를 저장해야 해서 메모리 사용량 큼	- DP 테이블을 추가로 사용해야 함
추천 상황	BFS 탐색 방식이 필요한 문제	이 문제에서 가장 적절한 방법!

---

🏆 결론

• BFS는 탐색 과정에서 많은 경우의 수를 고려해야 하므로 비효율적
• 위의 문제에선 DP 방식이 가장 빠르고 적합한 해결 방법