[프로그래머스 / Python] 등굣길

🧩 문제 설명 

 

 

🔐 문제 풀이 

0️⃣ 좌표 고려해서 문제 풀기 

위 사진과 같이 문제에서 좌표를 표현하는 방식과 일반적으로 좌표를 표현하는 방식이 달라 x, y를 뒤집어 문제를 풀어야한다. 

 

1️⃣ 최적의 경로의 수 구하는 방법 

현재칸의 최적의 경로의 수는 윗칸과 왼쪽칸의 최적의 경로의 수 합으로 구할 수 있다.

학교의 위치가 (x, y)라고 하면, (x-1, y)의 경로의 수 + (x, y-1)의 경로의 수 합으로 학교까지의 최적의 경로의 수를 구할 수 있다.

 

🫢 근데 1행과 1열의 경우에는 왼쪽 칸과 위쪽 칸이 존재하지 않는다.

이를 해결하기 위해 [n+1][m+1] 크기의 배열을 만들어 맨 왼쪽 줄과 맨 위쪽 줄의 값을 0으로 두고 사용하지 않을 예정이다.(0으로 두어 결과에 영향을 주지 않게 하자)

 

2️⃣ 물에 잠긴 경우 고려하기

puddles에 물에 잠긴 곳의 좌표가 주어져있다.

물에 잠기면 이동을 할 수 없기 때문에 물에 잠긴 곳을 마주쳤다면 해당 좌표의 값을 0으로 설정하도록 하였다.

 

 

💻 전체 코드 

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

def solution(m, n, puddles):
    # 주의: 문제에서 좌표와 일반적인 좌표와 반대로 되어 있음 
    
    dp = [[0] * (m + 1) for _ in range(n + 1)] # [n+1][m+1] 크기의 배열 생성
    dp[1][1] = 1 # 시작 위치  
    
    for x in range(1, n + 1):
        for y in range(1, m + 1):
            if x == 1 and y == 1:
                continue
            if [y, x] in puddles: # 물에 잠겼다면 이동할 수 없음
                dp[x][y] = 0
            else: 
                dp[x][y] = dp[x - 1][y] + dp[x][y - 1] # 현재 경로 = 왼쪽 칸 경로의 수 + 위칸 경로의 수 
    
    return dp[-1][-1] % 1000000007