[Programmers] level3 - 등굣길 (Python) : 동적계획법

▶등굣길 - 동적계획법 (level 3)

▶문제

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

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

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

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

 

 

▶제한사항

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

 

▶입출력 예

입출력 예 설명

 

▶풀이

n+1, m+1 2차원 배열을 생성해주고, 시작점인 [1][1]을 1로 설정해준다.

그다음에 배열 사이즈만큼 이중 for문을 해주면 된다.

이때 웅덩이가 있다면 그 지점은 지날 수 없기 때문에 0으로 해준다.

반복문에서 [i][j]가 아니라 [j][i]로 해서 0을 넣어준 이유는 좌표값이 서로 반대로 주어졌기 때문이다.

 

만약 그 길이 갈 수 있는 길이라면 왼쪽, 위쪽에서 올 수 있기 때문에 [i][j - 1]과 [i - 1][j]를 더 해주면 된다.

그다음에 %1,000,000,007 해주면 된다.

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

처음에는 뭔가 잘못되었는지 주어진 예제조차 정답이 나오지 않았다.

복잡하게 생각하고 문제를 풀려고 해서 그렇게 나온 거 같다.

다시 생각해보고 간단하게 푸니까 정답이 나왔다.

 

이 문제는 이중 for문으로 푸는 문제지만 그렇게 풀어도 효율성에서 통과된다.

저렇게만 풀어서 제출한다면 쉽게 100점이 나올 것이다.

아직은 효율성이 어떻게 해야 만점이 나오지 판단하지는 못하겠다.

어떤 문제는 직관적으로 반복문을 돌려도 효율성이 만점이 나오고,

어떤 문제는 그렇게 풀면 시간 복잡도가 좋지 않기 때문에 틀리게 나온다.

 

그냥 여러 가지 풀 수 있는 방법을 기억해두고 있으면 좋을 거 같다.