[프로그래머스][DP] 등굣길 python (201002)

 

 

1. 문제 설명 

** 유의해야할 제약 조건 

집이 있는 곳의 좌표는 (1, 1)   --> 1 인덱스 
학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.  --> puddle의 경우 y,x 로 입력 되는 것 

 

 

문제 핵심 : 

결국 학교까지 가게되는 최단 경로의 경우의 수 (number of path) 를 구해야하는 것 ! 

이 문제는 지난번에 푼 정수삼각형 문제와 거의 유사하다.  

모든 경로를 탐색하면서 최단 거리 (step of path) 를 찾는 BFS, DFS 가 아니라 (ex. 게임 맵 최단 거리)

각 칸마다, 거기까지 도달하는 최단 경로의 경우의 수를 저장해두는 DP문제 였던 것 (ex. 정수 삼각형) 

 

huidea.tistory.com/101

[프로그래머스][DP] 정수삼각형 python (200917)

 

 

 

** 정수 삼각형의 경우 가장 큰 값을 갖는 경로를 반환하는 방식이었고, 

이동때마다 가장 큰 값으로 옮기는 컨셉이어서 

다음 칸 값(a,b) 비교  --> 더 큰 쪽(a) 으로 이동  --> 누적합으로 해당 값 업데이트 (a update) 

 

결국 DP 문제들은 과거의 값들로 구성이 된다는 이 컨셉으로 문제가 풀리면  DP 리스트 만들면 됨. 

 

 

2. 풀이 

*** 제약 조건 안지켜서 처음에 에러 떴음. 

제약 1 : 집이 있는 곳의 좌표는 (1, 1)   --> 1 인덱스 
제약 2 :학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.  --> puddle의 경우 y,x 로 입력 되는 것 

 

 

def solution(m, n, puddles):

    MOD =  1000000007

    maps = [[0] * m for _ in range(n)]
    maps[0][0] = 1
    
    for x in range(n):
        for y in range(m):
            if ([y+1,x+1] in puddles) or ((x,y) == (0,0)): 
                continue # 다음 루프 !
            maps[x][y] = (maps[x-1][y] + maps[x][y-1]) % MOD
            
    return maps[-1][-1]

 

if 문에서 x,y 값이 바뀌어있고 1이 더해지는게 바로, 저 제약조건 때문임. ! 

조건에 맞게 요소를 바꾸고 puddles 입력에 해당 지점이 있는지 비교비교 

만약 puddles의 길이가 엄청 길다면 해당 자료형을 set으로 바꿔야 한다. 

 

why?  list, tuple, set, dictionary 에서 포함여부 확인하는 in (containment) 메소드의 시간복잡도 

list, tuple

• Average: O(n)
• 하나하나 순회하기 때문에 데이터의 크기만큼 시간 복잡도를 갖게 됩니다.

set, dictionary

• Average: O(1), Worst: O(n)
• 내부적으로 hash를 통해서 자료들을 저장하기 때문에 시간복잡도가 O(1)가 가능하고 O(n)의 경우에는 해시가 성능이 떨어졌을(충돌이 많은 경우) 때 발생합니다.

(출처 : twpower.github.io/120-python-in-operator-time-complexity)

 

 

 

3. 정리 

만약 어떤 경로의 경우의 수를 구하는 문제 (이때 모든 경로 탐색) or 각 단계에서의 최대 값 갖는 경루 

 ==> 이전 단계를 통해 다음 단계를 구해내는 방식  DP 

 

경로 중 최단 길이를 구하는 문제 or 경로를 구하는 문제라면 

==> 여기저기 들어갔다 나왔다 해야함 BFS, DFS

 

DP 와 BFS DFS 구분하는 문제들을.. 좀더 풀어봐야겟담...