[python] 프로그래머스 - 등굣길

출처 : 프로그래머스, https://programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

 

# 오른쪽과 아래로만 움직임
# 물웅덩이의 좌표가 주어짐
# 좌상단 집, 우하단 학교

# 집에서 학교까지 갈 수 있는 최단 거리의 개수 % 1000000007

 

 

먼저, 생각해야 할 부분

 

1. m x n

    좌표가 바뀌어있다. 

    이건.....알았는데..........문제 내의 모든 좌표가 바뀌어 있다.

    그러니까 물웅덩이 좌표도 바뀌어 있다.

    하필 예제가 [2, 2]인걸 보면 그냥 당하라고 낸 문제인 것 같다.

    꼼꼼하게 체크하자. 왠지 Lv. 3이더라.

 

2. 최단거리

    좌상단에서 우하단으로 오른쪽, 아래쪽으로만 움직이므로 어떻게 가든 무조건 최단 거리가 나온다.

    핵심은 최단 거리가 아니라 경로의 개수임을 파악하자.

---

 

풀이

 

def solution(m, n, puddles):
    # 오른쪽과 아래쪽으로만 움직이니까 모든 경로가 최단 경로
    # 즉, 최단 경로가 중요한게 아니라 그 타일까지 올 수 있는 경우의 수를 계산하는 것
    
    # 최단 경로의 개수 % 1000000007
    
    # D[i][j] = D[i-1][j] + D[i][j-1]
    D = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
    D[1][1] = 1
    
    puddles = set([tuple((p_r, p_c)) for p_c, p_r in puddles])
    
    #(1, 1) 제외, puddles 제외 하고 좌, 상 더해서 업데이트
    
    for i in range(1, n+1):
        for j in range(1, m + 1):
            if (i, j) == (1, 1) or (i, j) in puddles:
                continue
            
            D[i][j] = D[i-1][j] + D[i][j-1]
        
    return D[n][m] % 1000000007

 

---

 

Github