[프로그래머스💯] 코딩테스트 연습 > 등굣길

<프로그래머스 문제풀이>

<출처 : 프로그래머스(Programmers)>

 

---

해답)

 

def solution(m, n, puddles):
    path = [[0 for _ in range(m)] for _ in range(n)]
    path[0][0] = 1
    for y in range(n):
        for x in range(m):
            if [x+1, y+1] in puddles:
                print("x,y = > ", x, y)
                continue
            if x != m-1:
                path[y][x+1] += path[y][x]
            if y != n-1:
                path[y+1][x] += path[y][x]
    print(path)
    return path


solution(4, 3, [[2, 2]])

 

 

풀이)

이 문제는 동적 계획법의 대표적이면서도 간단한 문제입니다!

동적 계획법 문제의 기본은 중간점까지의 최적해를 계속해서 저장한 뒤 최종해를 구할 때도 써먹는다는 점입니다.

출발지에서 도착지까지의 최단경로를 한번에 구하는 것이 아니라,

부분적으로 각 칸들까지의 최단 경로를 모두 구해놓는 방식을 이용합니다.

 

도착지의 최단경로 비용은 도착지 바로 전 지점들의 경로 비용의 합이 됩니다.

마찬 가지로 각 지점의 최단경로 비용은 그 바로 전 지점들의 경로 비용의 합이 됩니다.

 

 

path 는 2차원 리스트로 각 지점의 최단경로 비용을 저장합니다.

그리고 puddles 인 경우를 제외하고 2중포문을 이용해 비용을 늘려줍니다.

 

* if [x+1, y+1] in puddles: 

에서 x, y 가 아닌 x+1 , y+1 인 이유는 puddles 는 1,1 이 시작점인 반면

제 코드의 인덱스는 0,0 이 시작점이기 때문입니다.

 

 

 

* 이 문제 및 로고의 저작권은 Programmers에 있습니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges