[Python][프로그래머스] 등굣길 / DP (Lv3)

🖇️ 링크 

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

프로그래머스

---

🗒️ 파이썬 코드 풀이

def solution(m, n, puddles):
    answer = 0 
    dp = [[0] * (m+1) for _ in range(n+1)]
    puddles = [[q,p] for p,q in puddles]

    for i in range(1,n+1):
        for j in range(1,m+1):
            
            if i == j == 1:
                dp[1][1] = 1
                continue
                
            if [i,j] in puddles : 
                continue
                
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) %1000000007
    
    return dp[-1][-1]

시간 복잡도 O( m * n)

 

1. 해당 코드가 가장 간단한 풀이 코드인 것 같다.

 

2. 편리함 (인뎅싱 + 첫 행& 첫 열 특수 케이스)을 이해 0 padding을 넣어준다.

→ 왠만하게 0 padding이 가능하다면 꼭 넣는게 편한 것 같다. 

 

3. 여기서 주의해야 할 점은 p,q를 뒤바꿔줘야 한다. 

→ 이거는 상상치도 못했다... 주어진 조건을 보고 m,n이 거꾸로 되어있는 것을 판단해야 함

 

4. i = 1, j = 1 인 경우는 집에 있을 때의 경우로 초기값 1을 설정해준다 .

 

5. puddles인 경우 continue로 스킵

→  puddles 세팅을 굳이 -1로  안하고, 이렇게 if ~ in으로도 가능

 

6. 그 외 일반적인 경우는왼쪽과 위쪽을 더해주면서 갱신하면 된다. 

 

 

🗒️ 그 외 풀이 

def solution(m, n, puddles):
    dp = [[0] * m for _ in range(n)]

    # puddles 설정
    puddles = [[q,p] for [p,q] in puddles]
    for i,j in puddles :
        dp[i-1][j-1] = -1

    dp[0][0] = 1

    for i in range(1,n):
        if dp[i][0] == -1 :
            dp[i][0] = 0
        else: 
            dp[i][0] = dp[i-1][0]

    for j in range(1,m):
        if dp[0][j] == -1 :
            dp[0][j] = 0
        else:
            dp[0][j] = dp[0][j-1] 

    for i in range(1,n):
        for j in range(1,m):

            if dp[i][j] == -1 : 
                dp[i][j] = 0
                continue 

            dp[i][j] = (dp[i][j-1]  + dp[i-1][j])% 1000000007

    answer = dp[-1][-1]

    return answer

 

1. 해당 문제 같은 경우 0 padding을 안한 풀이다.  

그래서 초기값 설정하는 코드가 추가로 들어가고, 다소 복잡하다.

 

2. 또한, puddle도 if ~ in으로 하지 않아서, puddle 값을 -1로 세팅을 해준다. 

 

3. 주의 할 점은 puddle을 지나면 꼭 0으로 초기화 해줘야한다. 

 

for i in range(n):
    if dp[i][0] == 0 :
        dp[i][0] = 1
    else: 
        break

for j in range(1,m):
    if dp[0][j] == 0 :
        dp[0][j] = 1
    else:
        break

 

맨처음 나는 위와 같이 풀이를 하였다. 

어차피 dp 초기값을 0으로 초기화 했고, puddle을 만나면 break 하면 되는거 아닌가 ? 

 

근데 이렇게 할 경우 -1이 다른 좌표 값에 영향을 미치기 때문에 꼭 0으로 초기화 해야한다, 

 

 

또 한가지 주의 사항은 puddle을 0으로 바꿔주고도 break 하면 안된다. 

왜냐하면 그 뒤에 또 다른 puddle이 있을 수 있기 때문이다. 

 

어찌보면 당연한 말인데, 내가 한 실수들이다...

또 해결하는데 시간이 오래 걸렸다.

---

📌  문제 코멘트 

이 문제를 포스팅 하는 이유는 다음과 같다.

• 맨 처음 BFS로 삽질 
• dp 사용했지만,padding을 하지 않음
• if ~ in으로 간단한 장애물 처리 
• q,p 장애물 좌표 반대로 표시

테스트 케이스의 경우들을 생각하지 못해 풀이하는데 오래걸렸다.

---

📚  문제 

---

가장 깔끔할 풀이 참고

https://dev-note-97.tistory.com/141