[programmers python] 42898 등굣길

 

https://programmers.co.kr/learn/courses/30/lessons/42898?language=python3 

코딩테스트 연습 - 등굣길

 

 

<problem>

 

 

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 

아래 그림은 m = 4, n = 3 인 경우입니다.

 

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다. 

 

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

 

 

 

<constraints>

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
  • m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

 

---

 

<example>

 

 

---

 

<solution ①>

 

예전에 학생 때 경우의 수 구하던 기억을 더듬어 보며 표를 통해 문제 이해 먼저 진행

 

	0	0	0	0
0	1(집)	1	1	1
0	1	0 (물 웅덩이)	1	2
0	1	1	2	4 (학교)

 

각 위치의 수는 왼쪽과 위의 숫자의 합이므로, 

학교에 가는 최단 거리는, 학교의 왼쪽의 수와 학교의 위쪽 위치의 수의 합이라고 할 수 있다. 

→ (m, n) = (m-1, n) + (m, n-1)

 

다이나믹 프로그래밍을 그냥 재귀함수만 사용한다면, 시간 복잡도가 매우 커질 것으로 예상 되므로, 

메모이제이션 기법 사용하여 해결하고자 함 (이것이 코딩 테스트다 with 파이썬 교재 chapter08 참고한 정리)

 

 

- 외곽지역까지 포함하여 memo라는 배열에 0으로 초기화

    - m, n이 각각 4, 3이라면, memo = [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

- memo[1][1] = 1 : 집 위치는 1로 설정

- for문 돌릴 때, n만큼 먼저, 그리고 m만큼 반복할 수 있도록 설정

    - 웅덩이인 경우, [1, 1]인 경우는 지나친다.

    - 나머지의 경우, 가로가 i, 세로가 j일 때 memo[i][j] = memo[i-1][j] + memo[i][j-1]

 

return (memo에 저장된 마지막 값을 1,000,000,007로 나눈 나머지)

 

---

 

ⓒ ⓞ ⓓ ⓔ

def solution(m, n, puddles):
    memo = [[0 for i in range(m+1)] for j in range(n+1)]
    
    memo[1][1] = 1
    
    for i in range(1, n+1):
        for j in range(1, m+1):
            if [j, i] in puddles:
                continue
            if i == 1 and j == 1:
                continue
            memo[i][j] = memo[i-1][j] + memo[i][j-1]
            
    return memo[m][n] % 1000000007

 

ⓣ ⓔ ⓢ ⓣ

 

 

 

---

 

ⓒ ⓞ ⓓ ⓔ

def solution(m, n, puddles):
    memo = [[0 for i in range(m+1)] for j in range(n+1)]
    
    memo[1][1] = 1
    
    for i in range(1, n+1):
        for j in range(1, m+1):
            if [j, i] in puddles:
                continue
            if i == 1 and j == 1:
                continue
            memo[i][j] = memo[i-1][j] + memo[i][j-1]
    
    return memo[n][m] % 1000000007

 

ⓣ ⓔ ⓢ ⓣ

 

---

 

처음에 헷갈렸던 부분처럼, memo에 n, m 대로 저장되었으므로

마지막에 출력할 때에도 memo[n][m] 을 나눈 나머지를 구해야함!!

 

처음에 그린 표처럼 초기화 시키도록 배열 다시 설정

 

 

---

 

ⓒ ⓞ ⓓ ⓔ

def solution(m, n, puddles):
    memo = [[0 for i in range(n+1)] for j in range(m+1)]
    
    memo[1][1] = 1
    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if [i, j] in puddles:
                continue
            if i == 1 and j == 1:
                continue
            memo[i][j] = memo[i-1][j] + memo[i][j-1]
    
    return memo[m][n] % 1000000007

 

ⓣ ⓔ ⓢ ⓣ

 

 

---

 

<solution ②> 다른 사람 풀이 참고

 

크게 달랐던 점은 물 웅덩이가 0개인 경우도 고려하고, 물웅덩이가 있는 곳은 배열에서 -1로 설정한 부분

- for문에서 동일하게 실행

    - [1, 1]인 경우 continue

    - 물웅덩이는 연산에 에러 발생할 수 있으므로 0으로 재설정

 

---

 

ⓒ ⓞ ⓓ ⓔ

def solution(m, n, puddles):
    memo = [[0]*(n+1) for i in range(m+1)]
    
    if puddles != [[]]:
        for a, b in puddles:
            memo[a][b] = -1
            
    memo[1][1] = 1
    
    for j in range(1, m+1):
        for k in range(1, n+1):
            if j == k == 1:
                continue
            if memo[j][k] == -1:
                memo[j][k] = 0
                continue
            memo[j][k] = memo[j][k-1] + memo[j-1][k]

    return memo[m][n] % 1000000007

 

 

ⓣ ⓔ ⓢ ⓣ

 

 

---

 

ⓒ ⓞ ⓓ ⓔ

def solution(m, n, puddles):
    memo = [[0]*(n+1) for i in range(m+1)]
            
    memo[1][1] = 1
    
    for j in range(1, m+1):
        for k in range(1, n+1):
            if j == k == 1:
                continue
            if [j, k] in puddles:
                continue
                
            memo[j][k] = memo[j][k-1] + memo[j-1][k]

    return memo[m][n] % 1000000007

 

ⓣ ⓔ ⓢ ⓣ

 

---

처음 초기화 시킬 때 for문을 한 번 사용한 것이 정확성과 효율성 시간을 줄였나 싶어서

-1로 초기화하는 과정 제거하고 해보았더니 두 가지 모두 영향을 주는 것을 알게 되었다. 

 

---

 

ⓕ ⓘ ⓝ ⓐ ⓛ    ⓒ ⓞ ⓓ ⓔ

 

def solution(m, n, puddles):
    memo = [[0]*(n+1) for i in range(m+1)]
    
    if puddles != [[]]:
        for a, b in puddles:
            memo[a][b] = -1
            
    memo[1][1] = 1
    
    for j in range(1, m+1):
        for k in range(1, n+1):
            if j == k == 1:
                continue
            if memo[j][k] == -1:
                memo[j][k] = 0
                continue
            memo[j][k] = memo[j][k-1] + memo[j-1][k]

    return memo[m][n] % 1000000007