코드카타 못 푼 문제 (재귀 함수) (최단 경로?)

매일 진행하는 코드카타

매일 진행하는 코드카타에 처음으로 못 푸는 문제가 나왔습니다!! 아주 좋네요!! 매일 못 푸는 문제가 나왔으면 좋겠습니다.

페어 프로그래밍 짝과 10분 가량 이야기해본 결과 재귀함수로 풀어야 한다는건 알겠는데 풀이를 모르겠다는 의견으로 합일되서 답을 보고 이해해보기로 했습니다. 구글링을 통해 아래 해답을 찾았고, 아래 해답을 한명씩 돌아가며 { 설명 : 키보드 } 역할을 해보았습니다. 그리고 마지막은 누가누가 외운거 빨리 치나 경쟁도 해봤습니다. ㅋㅋ

재귀함수 문제는 항상 어렵다고 느껴지는데, 이 문제는 이해하고 답을 외우는 형태로 가니 오히려 이해가 된것 같은 느낌이네요. 재귀함수 많이 풀어봐야겠습니다.

문제

양수로 이루어진 m x n 그리드를 인자로 드립니다.
상단 왼쪽에서 시작하여, 하단 오른쪽까지 가는 길의 요소를 다 더했을 때,
가장 작은 합을 찾아서 return 해주세요.

한 지점에서 우측이나 아래로만 이동할 수 있습니다.

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]

Output: 7

설명: 1→3→1→1→1 의 합이 제일 작음

Javascript

function minPathSum(grid) {
  const result = [];
  const underLen = grid.length - 1;
  const rightLen = grid[0].length - 1;

  function path(under, right, acc) {
    acc += grid[under][right];

    if (under < underLen && right < rightLen) {
      path(under, right + 1, acc);
      path(under + 1, right, acc);
    }
    if (under < underLen && right === rightLen ) {
      path(under + 1, right, acc);
    }
    if (under === underLen && right < rightLen) {
      path(under, right + 1, acc); 
    }
    if (under === underLen && right === rightLen) {
      result.push(acc);
    }

  }
  path(0,0,0);

  return Math.min(...result);
}

• 코드를 이해해보겠습니다.

위 코드는 경로상 모든 숫자를 합하는 path라는 함수를 재귀적으로 실행해서 모든 경우의 수를 다 합해주는 코드입니다.

이렇게만 이야기하면 이해가 안되는데, if문을 보면 좀 이해가 됩니다. if문의 조건을 보면 1) under, right이 모두 끝까지 못 간 경우, 2) under가 끝까지 못 간 경우, 3) right이 끝까지 못 간 경우, 4) right, under가 모두 끝까지 간 경우 (마지막) 로 나눠집니다.

1) under, right이 모두 끝까지 못갔으면 right +1, under +1로 각각 분기해서 나아갑니다.
2) under가 끝까지 못 간 경우면 under + 1 방향으로만 나아갑니다.
3) right이 끝까지 못 간 경우면 right + 1 방향으로만 나아갑니다.
4) right, under 모두 끝까지 도착하면, 해당 경로 상 숫자의 누적값인 acc를 result 배열에 담아줍니다.

path(0,0,0)은 재귀함수를 처음 실행해주는 main()과 같은 역할입니다.
그리고 return 값으로는 result에 담긴 모든 경로의 누적합 중 가장 적은 값을 리턴해줍니다.

아주 아주 멋진 코드네요!
재귀함수에 대한 이해도가 +1 된 느낌입니다 👍👍
앞으로 99번 정도만 재귀문제 풀면서 머리깨지면 재귀 고수가 될것만 같은 기분이 드네요 굳굳 ㅎㅎ