[프로그래머스] - 등굣길

문제

---

[프로그래머스] - 등굣길

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

프로그래머스

 

문제 이해

---

문제 설명

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

입출력 예

4

3

[[2, 2]]

4

이 문제는 주어진 예시가 너무 불친절하여 따로 정리를 해두었습니다.

1. 1,1 부터 시작 m,n이 종료 지점

2. puddles는 y,x가 거꾸로 되어 있다.

3. 문제가 요구한대로 배열을 [n+1][m+1] 개로 만들면 시간초과

4. 값을 더 할 때도 [nx][ny]가 들어갈 때 연산하게 되면 시간 초과..
-> 일반적인 예시와 다르게 설정해준 더러운 문제입니다..

 

알고리즘

---

Dynamic Programming을 활용하여 구하여 주면 됩니다.

1. 방문 여부를 따로 배열로 설정하여 두어 매번 접근하는 것이 아닌 빠르게 접근하여 확인할 수 있도록 Init

2. Dp table init 및 [0][0] = 1 로 설정

3. 좌,상에서 오는 경우에 대해 값 추가 후 나머지 처리

 

def solution(m, n, puddles):
    dp = [[0]*(m) for _ in range(n)]
    visited = [[0]*(m) for _ in range(n)]
    for y,x in puddles :
        visited[x-1][y-1]=1
    dp[0][0]=1
    dx,dy = [0,-1],[-1,0]
    
    for x in range(n):
        for y in range(m):
            if not visited[x][y]:
                for t in range(2):
                    nx,ny = x+dx[t] , y+dy[t]
                    
                    if 0<=nx<=n and 0<=ny<=m and not visited[x][y]:
                        dp[x][y]= (dp[x][y]+dp[nx][ny])%1000000007

    return dp[-1][-1]


solution(4,3,[[2, 2]])