문제설명

설계 과정

문제를 보자마자 DFS가 떠올랐고, 이를 적용해보려 했다.

• DFS이용
  DFS(row,col,sum)을 받는 함수로 만듬

1. 처음에 row가 끝까지 다 내려갔는지 체크
   -> 다 내려갔다면 maxSum보다 큰지 체크
   -> 크다면 maxSum = sum;
   -> 함수 종료
2. 0~3까지 -> DFS(row+1,i,sum+land[row][i]);
   단, col과 i가 같다면 패스
3. DFS(0,0,0)부터 시작

초기 코드

function solution(land) {
    var maxSum = 0;
    function DFS(row,col,sum){
        if(row===land.length){
            if(maxSum<sum){
                maxSum = sum;
            }
            return;
        }
        for(var i = 0;i<4;i++){
            if(col!==i){
                DFS(row+1,i,sum+land[row][i]);
            }
        }
    }
    DFS(0,0,0);
    return maxSum;
}

결과

결과는 처참했다.....
공부해보니, DFS가 답이 틀리게 나오진 않지만 계산 중복이 많아 시간복잡도가 커진다. 따라서 이를 해결하기 위해 중복 계산을 하지 않는 방법을 설계해야 한다.

개선 설계

이번엔 1행부터 끝까지 계산을 아래와 같이 진행
1. 현재 행을 같은 열을 제외한 이전 행의 모든 열의 값중 최대 값을 더해줌.
-> land[1][0] += Math.max(land[0][1],land[0][2],land[0][3]);
이를 반복적으로 수행하고,
2. 계산이 끝난 마지막 열중에 최댓값을 뽑아냄.

개선 코드

function solution(land) {
    
    var landLen = land.length;
    
    for(var i = 0; i<land.length-1;i++){
        land[i+1][0] += Math.max(land[i][1],land[i][2],land[i][3]);
        land[i+1][1] += Math.max(land[i][0],land[i][2],land[i][3]);
        land[i+1][2] += Math.max(land[i][0],land[i][1],land[i][3]);
        land[i+1][3] += Math.max(land[i][0],land[i][1],land[i][2]);
    }
    
    var maxSum = Math.max(land[landLen-1][0],land[landLen-1][1],land[landLen-1][2],land[landLen-1][3])

    return maxSum;
}

결과

이번 문제는 풀면서, 쉽게 풀 수 있던 방법을 두고서 어렵게 가려 했던게 시간초과 문제를 일으켰던 것 같다. 하지만 이 문제를 풀면서 기존에 어려워했던 DFS문제를 풀어보고, 정답까지 나오는 걸 확인해보니 자신감이 생기게 해주었다. 여러가지 알고리즘을 틀리고, 시간초과가 나더라도 시도해보는 것은 매우 좋은것 같다.