장애물이 있는 최소 경로 합

이제 각 칸에 값이 있고 모서리까지 가는 가장 저렴한 경로를 구하려고 합니다. 목표가 경로 개수 세기에서 비용 최소화로 바뀝니다.

dp[i][j]를 (i, j) 칸에 도달하는 최소 총비용이라고 하겠습니다. 같은 격자와 같은 이동을 사용하지만, 개수 대신 합을 추적합니다.

들어오는 두 이웃 칸 중 더 저렴한 것을 고른 다음 현재 칸의 값을 더합니다. 이 최솟값 선택이 점화식의 핵심입니다.

장애물은 그 위에 설 수 없는 칸입니다. 해당 칸의 비용을 무한대로 설정하면 그 칸을 지나는 경로가 최솟값이 될 수 없습니다.

격자에서 칸이 막힌 것으로 표시되면 해당 칸의 dp를 무한대로 설정하고 넘어가세요. 최솟값을 구하는 단계에서 자연스럽게 그 칸을 피하게 됩니다.

시작 칸 자체가 막혀 있다면 경로가 전혀 없습니다. 잘못된 비용을 반환하지 않도록 먼저 확인하세요.

시작 칸으로 들어오는 이웃은 없으므로 비용은 자신의 값뿐입니다. 반복문을 실행하기 전에 dp[0][0]을 설정하세요.

맨 위 행은 왼쪽에서만 이어지고 맨 왼쪽 열은 위쪽에서만 이어집니다. 격자 밖을 읽지 않도록 이 경계를 처리하세요.

무한대에 값을 더해도 무한대이므로, 사방이 막힌 칸은 INF 비용을 유지합니다. 도달할 수 없는 칸은 자동으로 그 사실을 나타냅니다.

최소 비용은 오른쪽 아래 칸에 있습니다. 그 값이 여전히 무한대라면 유효한 경로가 전혀 없는 것입니다.

더 작은 이웃 칸을 향해 항상 이동하면 막다른 길에 갇힐 수 있습니다. 탐욕적으로 한 단계만 살펴보는 방식이 아니라, 전체 DP만이 전역적으로 가장 저렴한 경로를 보장합니다.

모든 이웃을 특별히 처리하지 않고도 경로 DP가 막힌 칸을 피하게 하려면 어떻게 해야 할까요?

더 저렴한 이웃 칸에 현재 칸의 값을 더하고, 막힌 칸은 무한대로 설정한 다음 모서리를 확인하세요. 그곳이 INF라면 경로가 없습니다. 🧱