[Project Euler] 18. 삼각형을 따라 내려가면서 합이 최대가 되는 경로 찾기

18. 삼각형을 따라 내려가면서 합이 최대가 되는 경로 찾기

다음과 같이 삼각형 모양으로 숫자를 배열했습니다.

3
7 4
2 4 6
8 5 9 3

삼각형의 꼭대기부터 아래쪽으로 인접한 숫자를 찾아 내려가면서 합을 구하면, 위의 그림처럼 3 + 7 + 4 + 9 = 23 이 가장 큰 합을 갖는 경로가 됩니다.

다음 삼각형에서 합이 최대가 되는 경로를 찾아서 그 합을 구하세요.

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

참고: 여기서는 경로가 16384개밖에 안되기 때문에, 모든 경로의 합을 일일이 계산해서 답을 구하는 것이 가능합니다.
하지만 67번 문제에는 100층짜리 삼각형 배열이 나옵니다. 그런 경우에는 좀 더 현명한 풀이 방법을 찾아야겠지요.

75 95 64 17 47 82 18 35 87 10 20 04 82 47 65 19 01 23 75 03 34 88 02 77 73 07 63 67 99 65 04 28 06 16 70 92 41 41 26 56 83 40 80 70 33 41 48 72 33 47 32 37 16 94 29 53 71 44 65 25 43 91 52 97 51 14 70 11 33 28 77 73 17 78 39 68 17 57 91 71 52 38 17 14 91 43 58 50 27 29 48 63 66 04 68 89 53 67 30 73 16 69 87 40 31 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23 Click

작은 값을 구하는 거였으면 중간에 가지를 칠 수 있는 깊이 우선 탐색도 괜찮을 듯 하지만 최대값을 구하는 것이므로 어차피 전 노드를 탐색해야 하여 넓이 우선탐색을 이용했습니다.

너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다.
더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다. OPEN List 는 큐를 사용해야만 레벨 순서대로 접근이 가능하다.

( i, 0 )까지의 합 = ( i, 0 )의 값 + ( i-1, 0 )까지의 합.
 ( i, i )까지의 합 = ( i, i )의 값 + ( i-1 ,i-1 )까지의 합.
( i, j )까지의 합 = ( i, j )의 값 + [ { (  i-1, j-1 )까지의 합 } 또는 { ( i-1, j ) 까지의 합 } 중 큰 수 ] 라는 원칙에 의해 간단 탐색 구현.

<script>
/* 삼각형을 탐색하며 최대 값을 구함.
 * @param {Object} n : 삼각형의 층수.
 * @param {Object} nums : 삼각형이 저장 된 배열.
 */
function maxTriangleCourse(n, nums){
 //탐색을 하며 더한 값을 저장할 배열.
 var sum = new Array();
 
 //탐색. 
 sum[0] = new Array();
 sum[0][0] = nums[0][0];
 for(var i=1; i<n; i++){
  sum[i] = new Array();
  //(i,0)까지의 합. = (i,0) + (i-1,0)까지의 합. 
  sum[i][0] = sum[i-1][0] + nums[i][0];
  //(i,i)까지의 합. = (i,i) + (i-1,i-1)까지의 합.
  sum[i][i] = sum[i-1][i-1] + nums[i][i];
  for(var j=1; j<i; j++)
   /*(i,j)까지의 합. = (i,j) + (((i-1,j-1)까지의 합),
    ((i-1,j)까지의 합) 중 큰 수.)*/
   sum[i][j] = nums[i][j] 
    + ((sum[i-1][j-1]>sum[i-1][j])?sum[i-1][j-1]:sum[i-1][j]);
 }
 //max 값 구함.
 var max = 0;
 for(var i in sum[n-1])
  max = (max>sum[n-1][i])?max:sum[n-1][i];
 
 return max;
}
</script>

그런데 구현을 하고나니 댓글을 다신 분들 중에 아래서 부터 탐색을 하신 분이 계시더군요.
해당 방법으로 하면 위에 방법에 비해 최종 max값을 비교하는 과정이 빠지게 되어 더 빠를 수 있겠네요.
그래서 이 방식도 구현해 봤습니다.

<script>
/* 삼각형을 역으로 탐색하며 최대 값을 구함.
 * @param {Object} n : 삼각형의 층수.
 * @param {Object} nums : 삼각형이 저장 된 배열.
 */
function maxTriangleCourseInverse(n, nums){
 //탐색을 하며 더한 값을 저장할 배열.
 var sum = new Array();
 
 //가장 아래 층 초기화.
 sum[n-1] = new Array();
 for(var i in nums[n-1])
  sum[n-1][i] = nums[n-1][i];
 
 //역탐색.
 for(var i=n-2; i>=0; i--){
  sum[i] = new Array();
  for(var j=0; j<=i; j++)
   /*(i,j)까지의 합. = (i,j) + (((i+1,j)까지의 합),
    ((i+1,j+1)까지의 합) 중 큰 수.)*/
   sum[i][j] = nums[i][j]
    + ((sum[i+1][j]>sum[i+1][j+1])?sum[i+1][j]:sum[i+1][j+1]);
 }
 return sum[0][0];
}
</script>