[프로그래머스] 등굣길

문제 정보

• 프로그래머스 문제 링크
• 난이도 : level 3

 

해결 방법

왼쪽 위 (1, 1) 부터 오른쪽과 아래로만 이동할 수 있는 최단거리 문제로 중학교(?) 교과 과정에서 많이 풀던 경로 문제입니다. 왼쪽 위부터 갈 수 있는 경우의 수를 표시하면서 왼쪽과 위의 경우의 수를 순차적으로 합산하여 구현할 수 있습니다. 그래서 Dynamic Programming 알고리즘을 사용해 구현했습니다.

처음 구현할 때는 두 가지 문제점이 있었는데 첫 번째는 중간에 웅덩이가 있을 경우 지나가지 못하는 경우를 중복으로 세서 물 웅덩이가 많을 경우 음수로 나와버리는 경우를 발견했는데 물 웅덩이에서의 경로의 수를 0 으로 세팅하여 해결했습니다. 두 번째는 위에서 기술했듯이 예전 교과 과정에서 많이 풀던 방식으로 인해 생긴 문제인데 x == 1 or y == 1 인 경우를 계산하지 않고 그냥 1 로 세팅하여 물 웅덩이가 중간에 있는 경우가 고려되지 않아서 답 보다 많은 경로의 수가 나오게 되었습니다.

위 두 가지를 해결한 후에는 정확도나 시간에 별 문제없이 통과했습니다. 해보진 않았지만 효율성 테스트가 있던 것으로 보아 메모이제이션 기법을 사용하지 않았다면 효율성 테스트에서 통과하지 못했을 것으로 보입니다. 

 

소스 코드

# 틀림
def solution(m, n, puddles):
    answer = 0
    memoization = {} # (x, y) : 경로 수 key-value > dict 형 자료형
    
    # (0, 0) -> (x, y) 이동시 
    def dp(x, y):
        if((x, y) in memoization):
            return memoization[(x, y)]
        
        if(x == 1):
            memoization.update({(x, y) : 1})
        elif(y == 1):
            memoization.update({(x, y) : 1})
        else:
            
            newDp = dp(x - 1, y) + dp(x, y - 1)
            memoization.update({(x, y) : newDp})
            
        return memoization[(x, y)]
    
    totWay = dp(m, n)
    #print('totWay:' + str(totWay))
    
    for puddle in puddles:
        x1 = puddle[0]
        y1 = puddle[1]
        toPuddleWay = dp(x1, y1)
        toSchoolWay = dp(m - x1 + 1, n - y1 + 1)
        #print('toPuddleWay:' + str(toPuddleWay) + ' / toSchoolWay:' + str(toSchoolWay))
        
        curPuddleWay = toPuddleWay * toSchoolWay
        totWay -= curPuddleWay
    
    answer = totWay % 1000000007
    return answer

# 틀린 이유
# 1. 전체 경로 수 - 웅덩이로 지나는 경로 수
#    >> 거쳐서 갈 수 있으면 중복되는 경로가 있을 수 있어서 puddles 각각 빼면 안됨
# 2. x == 1, y == 1 인 인경우 중간에 puddles 가 있다면 1 이 아니라 0 으로 계산해야함

def solution(m, n, puddles):
    answer = 0
    memoization = {} # (x, y) : 경로 수 key-value > dict 형 자료형
    
    # (0, 0) -> (x, y) 이동시 
    def dp(x, y):
        # 이미 저장된 값일 경우
        if((x, y) in memoization):
            return memoization[(x, y)]
        
        # 웅덩이일 경우
        for puddle in puddles:
            if(puddle[0] == x and puddle[1] == y):
                memoization.update({(x, y) : 0})
                return memoization[(x, y)]
            
        if(x == 1 and y == 1):
            memoization.update({(x, y) : 1})
        elif(x == 1):
            memoization.update({(x, y) : dp(x, y - 1)})
        elif(y == 1):
            memoization.update({(x, y) : dp(x - 1, y)})
        else:
            newDp = dp(x - 1, y) + dp(x, y - 1)
            memoization.update({(x, y) : newDp % 1000000007})
            
        return memoization[(x, y)]
    
    totWay = dp(m, n)
    #print('totWay:' + str(totWay))
    #print('memoization:' + str(memoization))
    
    answer = totWay % 1000000007
    return answer

 

참고 자료

• 동적 계획법(Dynamic Programming) (수정: 2019-02-07)