[알고리즘] 백준 파이썬 14430 자원캐기

 

📍 문제 탐색하기

이번 문제는 WOOK이라는 로봇이 탐사 영역에서 최대한 많은 자원을 수집하는 문제이다.
WOOK은 (1,1)에서 시작해 (N,M)로 이동하며, 오른쪽과 아래쪽으로만 이동할 수 있다.
로봇은 탐사 영역의 각 칸에 자원이 있다면 이를 수집하며, 마지막 칸 (N,M)에 도달했을 때 최대 자원의 개수를 출력해야 한다.

---

문제 조건

1. 탐사 영역의 크기는 N×M, 각 칸에는 1(자원 있음) 또는 0(빈 땅)이 표시된다.
2. N,M≤300: 최대 300×300=90,000칸까지 처리 가능하다.
3. 시간 복잡도 O(N×M)로 해결 가능!

---

📍 코드 설계하기

입력 처리

1. 탐사 영역의 크기 N,MN, MN,M과 탐사 영역 데이터를 입력받는다.
2. area[r][c]는 (r,c) 위치의 자원 개수를 나타낸다.

DP 점화식 설계

1. DP 정의:
   • dp[r][c]: (r,c)까지 이동했을 때 수집할 수 있는 최대 자원 개수이다.
2. 이동 경로:
   • 현재 칸으로 올 수 있는 경로는 왼쪽(dp[r][c−1]dp[r][c-1]dp[r][c−1])과 위쪽(dp[r−1][c]dp[r-1][c]dp[r−1][c]) 두 가지이다.
   • 문제에선 오른쪽과 아래쪽으로만 이동할 수 있다고 했으므로 내 기준에서 왼쪽과 위쪽에서 올 수 있는 것이다. 중요!!!
3. 점화식: dp[r][c]=max⁡(dp[r−1][c],dp[r][c−1])+area[r][c]
   • dp[r−1][c]: 위쪽 칸에서 내려온 경우.
   • dp[r][c−1]: 왼쪽 칸에서 오른쪽으로 이동한 경우.
   • 현재 칸의 자원 개수 area[r][c]를 더해 업데이트한다.
4. 초기값:
   • dp[0][0]=area[0][0]: 시작 위치의 자원 개수 그대로 초기화한다.
5. 구현:
   • 탐사 영역의 각 칸을 순차적으로 탐색하며, 점화식을 기반으로 dp배열을 업데이트한다.
     마지막 칸 dp[N−1][M−1]이 최대 자원 개수이다.

---

📍 시도 회차 및 수정 사항

1차 시도 (틀림) ❌

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

area = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * M for _ in range(N)]

# 오른쪽, 아래
dr = [0, 1]
dc = [1, 0]

def dfs(r, c):
    visited[r][c] = True
    
    for i in range(2):
        nr = r + dr[i]
        nc = c + dc[i]
        
        if 0 <= nr < N and 0 <= nc < M:
            if not visited[nr][nc]:
                area[nr][nc] += area[r][c]
            elif area[nr][nc] < area[r][c]:
                area[nr][nc] = area[r][c]
            dfs(nr, nc)

dfs(0,0)
print(area[N-1][M-1])

문제점:

• DFS 사용으로 발생한 문제:
  • 탐색 순서에 따라 값이 중복 계산되거나 덮어씌워져 최적 경로를 보장하지 못한다.
  • 예를 들어, 왼쪽과 위쪽에서 올 수 있는 값 중 더 큰 값을 고려하지 않고 탐색 순서대로 값을 갱신한다.
  • 또한 내 기준 왼쪽 위쪽을 생각하지 못하고 평소 dfs 풀던 것처럼 오른쪽, 아래로 dfs로 가는 것으로 풀어서 틀렸다.

---

2차 시도 (맞음) ✅

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

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

# 왼쪽, 위
dr = [0, -1]
dc = [-1, 0]

for r in range(N):
    for c in range(M):
        max_num = 0
        
        for k in range(2):
            nr = r + dr[k]
            nc = c + dc[k]
            
            if 0 <= nr < N and 0 <= nc < M:
                max_num = max(max_num, area[nr][nc])
                
        area[r][c] += max_num          

print(area[N-1][M-1])

 

---

수정 내용

1. DFS 삭제:
   • DFS는 탐색 경로에 따라 값이 덮어씌워질 가능성이 있었다.
   • 반복문과 DP를 사용하여 각 칸에 대해 최댓값을 갱신하는 방법으로 수정해주었다.
2. 왼쪽과 위쪽 칸 고려:
   • 각 칸에서 올 수 있는 두 가지 경로(왼쪽, 위쪽) 중 최댓값을 선택하여 갱신해주었다.
   • 이를 통해 탐사 영역의 모든 칸을 정확히 계산할 수 있었다!

---

📍 느낀점

문제의 조건 활용을 잘하자!

 오른쪽과 아래로만 이동한다는 제약 조건을 잘 활용하여 DP 점화식을 설계하니 문제가 단순화되었다.