DFS/다이나믹 - 땅따먹기

이번 문제는 프로그래머스 사이트에 공개된 문제입니다.

문제

https://programmers.co.kr/learn/courses/30/lessons/12913

분석/설계

땅따먹기 특수 규칙에 의해 주어진 land 2차 배열을 나올수 있는 경우의 수를 전부 탐색해서

최대값을 얻어야겠다고 생각했고, 바로 DFS를 떠올렸습니다.

하지만 DFS 사용 시 행의 개수가 100,000 이기 때문에 효율성 걸려서 코드 제출을 통과할수 없습니다.

 

구현 코드

// DFS 버전
public class Solution {

  static boolean[][] visited;
  static int res = 0;

    static int solution(int[][] land) {
        int answer = 0;
        visited = new boolean[land.length][4];
        pick(0,0,land);	
        answer = res;
        return answer;
    }
    
    static void pick(int row, int sum, int[][] land ) {
    	if(row == land.length) {
    		res = Math.max(res, sum);
    		return;
    	}
    	
    	for(int i=0; i<4; i++) {
    		if(!visited[row][i]) {
    			sum += land[row][i];
    			if(row < land.length-1) visited[row+1][i] = true;
    			pick(row+1, sum, land);
    			if(row < land.length-1) visited[row+1][i] = false;
    			sum -= land[row][i];
    			
    		}
    	}
    }
}

정답 코드(다른 사람의 코드와 비교)

class Solution {
    int solution(int[][] land) {
        int answer = 0;
     
        for(int i=1; i< land.length; i++) {
        	land[i][0] += Math.max(land[i-1][1], Math.max(land[i-1][2], land[i-1][3]));
        	land[i][1] += Math.max(land[i-1][0], Math.max(land[i-1][2], land[i-1][3]));
        	land[i][2] += Math.max(land[i-1][0], Math.max(land[i-1][1], land[i-1][3]));
        	land[i][3] += Math.max(land[i-1][0], Math.max(land[i-1][1], land[i-1][2]));
        }
        
        for(int i=0; i<4; i++) {
        	answer = Math.max(answer, land[land.length-1][i]);
        }
        
        return answer;
    }
}

비교/정리

DFS 사용 시 모든 경우의 수를 반복해서 계산하기 때문에 효율성이 떨어져 코드 제출 시 시간 초과가 발생합니다.

다이나믹 프로그래밍을 사용하면 효율성을 개선하고 비교적 쉽게 풀수 있는 문제입니다.

 

참고

https://programmers.co.kr/learn/courses/30/lessons/12913