프로그래머스 등굣길 코드 및 해설 (파이썬)

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

코딩테스트 연습 - 등굣길

 

town이라는 딕셔너리를 정의하고, key에는 각 위치의 좌표, value에는 각 위치에 도달하기까지 가능한 모든 경우의 수를 저장했습니다. 오른쪽과 아래쪽으로만 움직일 수 있기 때문에 현재 위치의 왼쪽과 위쪽의 값을 더해 현재 위치의 값을 갱신했습니다.
이때 왼쪽이나 위쪽에 길이 없어 index Error가 날 수 있는 곳은 길이 없는 곳은 제외하고 길이 있는 곳의 값을 그대로 가져오도록 했고, 물 웅덩이가 있는 곳의 값은 모두 0으로, 출발지인 집은 값을 1로 초기화했습니다.

 

def solution(m, n, puddles):
    # 학교가 있는 곳의 좌표가 (m,n)이므로 (열,행)
    # (행,열)로 좌표를 바꿔주기 위해 순서 바꿈 
    puddles = [(puddle[1]-1, puddle[0]-1) for puddle in puddles]
    
    town = {}
    for i in range(n):
        for j in range(m):
            # 집
            if (i,j) == (0,0):
                town[(i,j)] = 1
                
            # 물 웅덩이 
            elif (i,j) in puddles:
                town[(i,j)] = 0
                
            # 왼쪽에 길이 없는 경우
            elif j-1 < 0:
                town[(i,j)] = town[(i-1,j)]
            
            # 위쪽에 길이 없는 경우
            elif i-1 < 0:
                town[(i,j)] = town[(i,j-1)] 
            
            # 왼쪽과 위쪽 모두 길이 있는 경우 
            else:
                # 왼쪽과 위쪽의 길까지 다다르는 경우의 수를 더함 
                town[(i,j)] = town[(i,j-1)] + town[(i-1,j)]
    
    
    return town[(n-1, m-1)] % 1000000007