프로그래머스 LV3 등굣길

문제 유형 : 동적계획법 (DP) 
문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

 

 

1. 문제 해결 법 

• 미로찾기와 비슷한 문제라고 생각해서 그렇게 풀려고 했다. 그런데 몇 년전에 풀었던 DFS 미로찾기 문제 때 했던 방식이 생각이 나질 않았다...! 역시 복습을 안하면 안될 것 같다라는 생각을 했다.
• 먼저 생각한 풀이에서는 오른쪽으로 가면 (i+1,j) , 아래로 가면 (i,j+1)인 것을 생각했고 이 과정을 저장해가며 이어가는  방식을 사용해야 함을 알았다. 
• 그래서 웅덩이가 없다는 조건 하에 오른쪽과 아래로 갈 때만이 최단거리이므로 이 과정을 나누어서 계산했다. 그리고 각각의 경우에서 count를 더해주는 조건을 생각했다.  그 후 count 값 중 최소값을 result_count에 더해주려고 했다.
• 결과적으로 위 과정을 나눌 필요가 없었고 count 대신 동적계획법으로 저장해두는 방식을 사용해야 함을 깨달았다. 
• 그런데 웅덩이 조건을 어떻게 제약 할 지를 몰라 한참 헤맸고 결과적으로 구글링의 도움을 얻게 되었다..
• 집 = 1 , 길 = 0 , 웅덩이 = -1 로 설정해주었다. 그래서 길을 지날 때는 0이기 때문에 이런 식으로 진행하면 미로 찾기와 동일하게 경로를 계산할 수 있었다. 웅덩이를 -1 (꼭 -1이 아니여도 될 것 같다) 로 설정해주고 웅덩이를 만났을 때는 count 하지 않도록 continue 해주었다. 그리고 다음 덧셈에 영향이 가지 않게 기존 -1 처리 된 것을 0으로 바꾸어 주었다.(Feedback) 

2. 에러 결과 

실패 사진 1

 

=> arr[i][j] == -1 일 때 그냥 continue를 해주어서 빠져 나갔더니 다음 덧셈 결과에 -1 로 시작해서 지장이 생긴 것 같았다. 그래서 arr[i][j] = 0 으로 길 처럼 초기화 해주었다. 

=> 그리고 이 에러 이전에 indexError가 발생했던 것은 arr 배열 초기화로 해결해주었다. 꼭 주어진 범위를 지정해서 초기화 해줘야함을 깨달았다. 

3. 최종 코드 

def solution(m, n, puddles):
    answer = 0
    arr = [[0] * (m+1) for _ in range(n+1)]
    arr[1][1] = 1 
    for j,i in puddles :
        arr[i][j] = -1
    for i in range(1, n+1):
        for j in range(1,m+1):
            if arr[i][j]==-1:
                arr[i][j] = 0
                continue
            else:
                arr[i][j] += arr[i-1][j] + arr[i][j-1] 
        answer = arr[i][j] % 1000000007
    return answer

 

 

4. Feedback 

• 미로찾기를 해결했던 방식이 생각나질 않았다. 문제를 어떻게 구현 할 지는 머릿속으로는 알겠는데 코드로 구현하기 너무 어려웠다. dfs, bfs는 자료구조 시간에 과제로도 진행했던 만큼 까먹지 말도록 복습 하도록 하자
• 이런 m,n 처럼 범위가 정해진 미로 찾기나 경우의 수를 따지려 할 때는 항상 배열을 초기화 하는 습관을 가지자
  arr = [[0] * (m+1) for _ in range(n+1)] 
• 끝까지 코드는 작성해보고 그 뒤로 구글링을 하자. 오늘 웅덩이 제약 조건이 생각나질 않아서 그 조건 빼고 코딩을 한 후 채점 후에 구글링을 하니 이해가 더 빨리 되었다. 몰라도 시간 제한 걸고 끝까지 시도해보는 습관과 끈기를 가지자. 

 

 

출처 : https://velog.io/@dhelee/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%93%B1%EA%B5%A3%EA%B8%B8-Python-%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8DDP

[프로그래머스] 등굣길 / Python / 다이나믹 프로그래밍(DP)