[프로그래머스, JAVA] 땅따먹기

[ 문제 ]

땅따먹기 게임을 하려고 합니다.

땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다.

1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다.

 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면,

| 1 | 2 | 3 | 5 |
| 5 | 6 | 7 | 8 |
| 4 | 3 | 2 | 1 |

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.


마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요.

위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아

16점이 최고점이 되므로 16을 return 하면 됩니다.


제한사항 

행의 개수 N : 100,000 이하의 자연수

열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.

점수 : 100 이하의 자연수

입출력 예

land    [[1,2,3,5],[5,6,7,8],[4,3,2,1]]

answer  16

간단한 문제로 생각해서 풀었는데... Test Case는 맞았지만 나머지는 모두 틀려서 0점...
그 이유는 현재 땅 중 방문하지 않았으며 그중에서 가장 큰 땅을 선택하는 Greedy 방식으로 풀어서 전부 틀렸습니다.. (접근 자체가 FAIL)

<Greedy>

// 기존 실패 코드 Greedy 방식
class Solution {
	boolean[] visited = new boolean[4];
	int result = 0;
	int col;

	int solution(int[][] land) {

		col = land.length;

		getMaxInNotVisitedPrevRow(land, 0, -1);

		return result;
	}

	public void getMaxInNotVisitedPrevRow(int[][] land, int colNum, int prevMaxIdx) {
		if (colNum == col)
			return;

		int idx = 0;
		int max = Integer.MIN_VALUE;

		if (colNum == 0) {
			for (int i = 0; i < 4; i++) {
				if (max < land[0][i]) {
					max = land[0][i];
					idx = i;
				}
			}
			visited[idx] = true;
		} else {
			for (int i = 0; i < 4; i++) {
				if (!visited[i] && max < land[colNum][i]) {
					max = land[colNum][i];
					idx = i;
				}
			}
			visited[prevMaxIdx] = false;
			visited[idx] = true;
		}

		result += max;

		getMaxInNotVisitedPrevRow(land, colNum + 1, idx);
	}
}

이후에 DP를 이용해서 매 단계마다 가장 큰 값이 아닌 이전의 방문 경로 중 현재 방문 위치와 겹치지 않으면서 가장 큰 값을 선택하는
방식으로 바꿨습니다.

<DP>

class Solution {
	int[][] dp;
	int[][] map;
	// boolean[] visited = new boolean[4];

	int solution(int[][] land) {
		int answer = 0;

		dp = new int[land.length][land[0].length];
		map = land;

		int col = dp.length;
		int row = dp[0].length;

		for (int i = 0; i < col; i++) {
			for (int j = 0; j < row; j++) {
				dp[i][j] = map[i][j];
			}
		}

		for (int i = 0; i < 4; i++) {
			calculate(1);
		}

//		for (int i = 0; i < col; i++) {
//			for (int j = 0; j < row; j++) {
//				System.out.print(dp[i][j] + " ");
//			}
//			System.out.println();
//		}

		int max = Integer.MIN_VALUE;
		for (int i = 0; i < 4; i++) {
			if (max < dp[col - 1][i])
				max = dp[col - 1][i];
		}

		return max;
	}

	void calculate(int colNum) {
//		int idx = -1;
		if (colNum >= dp.length) {
			return;
		}

		for (int i = 0; i < 4; i++) {
			for(int j=0;j<4;j++) {
				if(i == j)
					continue;
				
				if (dp[colNum][i] < map[colNum][i] + dp[colNum - 1][j]) {
//					idx = i;
					dp[colNum][i] = map[colNum][i] + dp[colNum - 1][j];
				}
			}
			// dp[colNum][i] = Math.max(dp[colNum][i],map[colNum][i] +
			// map[colNum-1][prevIndex]);
		}

		calculate(colNum + 1);
	}
}

 

바로 Greedy를 떠올리다니... 조금 더 숙고하고 생각했으면 혹시라도 DP를 먼저 떠올렸을 수도 있었을 텐데요 심지어
간단한 DP일 뿐인데도 머리 쥐어짜면서 짰습니다.. 열심히 하겠습니다.. 빛이 보이는 날까지