[코딩테스트] 동적계획법(Dynamic Programming) - 등굣길

---

문제

 

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

프로그래머스

 

길 찾기 경우의 수 문제.

 

중간에 가지 못하는 길이 있을 경우 어떻게 처리해야 하는지가 중요하다.

 

 

문제에서 그림을 잘못 그렸음. m  x n 크기라고 해놓고 n x m 그림을 그렸음.

 

---

전략

 

01. 수학적인 풀이

 입출력 예제에서 가로로 두번, 세로로 세번 건너는 모든 경우의 수를 센 뒤 웅덩이를 지나는 경우의 수를 빼면 되므로 [가로, 가로, 세로, 세로, 세로]의 경우의 수를 구해주면 된다. 여기서는 가로, 세로 같은 것들이 있으므로 f(5)/f(3).f(2) 즉 같은 것이 있는 순열 공식을 쓰면 된다.

 

 하지만 웅덩이를 지나는 경우의 수를 빼려고 보니 웅덩이가 여러 개 겹쳐 있을 때 컴퓨터로 어떻게 처리를 해줄 것인지가 문제였다. 웅덩이의 위치가 나열된 리스트를 순회하면서 각 경우의 수를 뺀다 쳐도 어쨌든 각 경우의 수에 대한 저장이 필요했다. 이 부분이 오히려 번거로울 것이라고 생각해 그만 뒀다.

 

 

02. 동적 프로그래밍(DP)

 

수학 문제 풀 때 흔히 했던 각 단계마다 경로를 더하는 방식으로 푸는 것. m x n 크기의 리스트를 만든 뒤 모든 값을 1로 세팅한다. 그리고 웅덩이는 0으로 세팅해주고 m x n 크기의 리스트를 차례로 순회하면서 이전 값들을 더해준다.

 

 

---

풀이

 

def solution(m, n, puddles):
	# 맵 세팅
    road = [[1 for _ in range(n)] for _ in range(m)]
    
    # 웅덩이 세팅
    for y, x in puddles:
    	# 일반적인 경우 웅덩이를 0으로 세팅해준다.
        road[y - 1][x - 1] = 0
        
        # x, y가 1일 경우 나머지 부분도 제외
        if y == 1:
            for x_ in range(x, n):
                road[y - 1][x_] = 0
        
        if x == 1:
            for y_ in range(y, m):
                road[y_][x - 1] = 0
    
    # 이중 반복문으로 순회하면서 왼쪽 값과 위의 값을 차례로 더해나간다
    for i in range(1, m):
        for j in range(1, n):
            if road[i][j] != 0:
                road[i][j] = road[i - 1][j] + road[i][j - 1]
    
    return road[-1][-1] % 1_000_000_007

 

  주석으로 간단히 달아뒀지만, 웅덩이 세팅할 때 x, y가 1일 경우에 (즉 첫번째 열이나 행일 경우) 그 다음 행, 열은 지날 수가 없다.

 

 위의 그림처럼 첫 열 중간에 웅덩이가 있다면 그 다음 길도 이용할 수 없다. 따라서 첫 열이나 행일 경우 중간에 웅덩이가 있다면 그 뒤 길까지 전부 0으로 처리해줘야 한다.

 

if y == 1:
    for x_ in range(x, n):
        road[y - 1][x_] = 0

if x == 1:
    for y_ in range(y, m):
        road[y_][x - 1] = 0

 

 따라서 이렇게 두 케이스의 경우에 각각 반복문으로 그 뒤 길들을 0으로 만들어 주었다.

 

if y == 1:
    road[y - 1][x:] = [0 for _ in range(n - x)]

 

 처음엔 List comprehension으로 이렇게 편하게 만들어주려고 했는데, 계속 IndexError가 떴다. 지금 생각해보니 가장 마지막 열이나 행에 웅덩이가 있을 경우 range(0)이 돼서 에러가 발생한 것 같다.

 

 

효율성 테스트

 

 

---

다른 사람의 풀이

 

def solution(m, n, puddles):
    answer = 0
    info = dict([((2, 1), 1), ((1, 2), 1)])
    for puddle in puddles:
        info[tuple(puddle)] = 0

    def func(m, n):
        if m < 1 or n < 1:
            return 0
        if (m, n) in info:
            return info[(m, n)]
        return info.setdefault((m, n), func(m - 1, n) + func(m, n - 1))
    return  func(m, n) % 1000000007

 

 딕셔너리와 재귀함수를 이용해 푼 풀이다. 주목할만한 포인트는 (1) 각 경로를 튜플 형식으로 딕셔너리에 추가해 계산 반복을 막은 점, (2) 재귀 함수의 base case 조건, (3) dict.setdefault()를 이용해 각 포인트의 (m, n)이 존재하지 않으면 (=웅덩이나 첫번째 경로가 아니면) 이전 값들을 더하는 방식이다.

 

 재귀를 이용한 파이썬스러운 풀이였다.

 

효율성 테스트