[프로그래머스] (LV3) 등굣길

등굣길

Python3

문제 설명

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 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개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

입출력 예

m	n	puddles	return
4	3	[[2, 2]]	4

입출력 예 설명

풀이

---

python

def solution(m, n, puddles):
    inf = 1000000007
    dist = [[0]*(m+1) for _ in range(n+1)]
    dist[0][1] = 1 
    for p in puddles:
        dist[p[1]][p[0]] = inf

    for row in range(1,n+1):
        for col in range(1,m+1):
            if dist[row][col] == inf:
                dist[row][col] = 0
            else:
                dist[row][col] = (dist[row-1][col] + dist[row][col-1]) % inf

    return dist[n][m]

설명

---

DP로 풀어야 효율성 케이스를 통과할 수 있는 문제다.

divide and conquer를 이용한 재귀함수로 아주 간단히 풀 수 있지만, 효율성에서 통과되지 못했다.

메모리를 활용한 DP 풀이로 다시 풀었을때도 몇가지 케이스를 계속 틀렸는데, 전체 맵을 1로 셋팅하고 i==0 이거나 j==0 인 경우를 무시하고 지나가서 였다.

그러다보니 i==0 이거나 j==0 에서 생긴 웅덩이 다음 길에서 1로 값이 세팅되어 있는 문제점이 있었다. 이를 해결하기 위해 다시 0부터 모든 인덱스를 탐색하며 풀이했다.

간단하게 DP의 핵심 개념을 연습하기 좋은 문제다.

풀이 수정 (2021.08.24)

• 0 ~ n 까지의 인덱스 할당(총 n+1개)
• (1,1) 노드부터 DP식으로 계산 (윗 노드 + 왼쪽 노드)
• 웅덩이를 따로 마킹(inf)하고 추후 이를 0으로 할당
• 이를통해 복잡한 조건문 없이 풀이 가능