프로그래머스 > 땅따먹기 (Python 3)

1. 문제 설명

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

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

 

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

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

 

예)

|1|2|3|5|

|5|6|7|8|

|4|3|2|1|

1행에서 네번째 칸 (5)를 밟았다면, 2행의 네번째 칸 (8)은 밟을 수 없다.

 

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최댓값을 반환하라.

 

 

 

2. 코드

(1) 1차 시도 - 런타임 에러

answer = 0

def dfs(land, row, col, tot):
    global answer
    tot += land[row][col]

    if row == len(land) - 1:
        if answer < tot:
            answer = tot
        return 
    

    for i in range(4):
        if i == col:
            continue
        dfs(land, row+1, i, tot)
    
    
def solution(land):
    global answer
    
    for col in range(4):
        dfs(land, 0, col, 0)
    
    return answer

 

 

(2) 2차 시도 - DP

def solution(land):
    for i in range(1, len(land)): # 행 반복
        for j in range(4): # 열 반복
            land[i][j] += max(land[i-1][:j] + land[i-1][j+1:])
    
    return max(land[-1])

 

 

 

3. 설명

우선 처음에 짠 코드는 깊이 우선 탐색 (DFS) 방법을 사용해서 구현했다.

재귀 함수로 열을 반복하며 (단, 연속된 동일한 열은 제외) sum을 누적하는 방식으로 했는데,

재귀로 호출되면서 알 수 없는 런타임 에러가 떴다.. (반례도 다 조사했을 때 문제 없었다ㅠㅠ)

 

그래서 다이나믹 프로그래밍으로 다시 구현했다.

이전 행에서의 최댓값을 뽑아서 현재 행에 더하는 방식으로 하여,

맨 마지막 행에서의 최댓값을 택하면 답이 된다!