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

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

 

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

입출력 예

입출력 예 설명

---

[내 풀이]

- 기본 값은 0으로 설정

- 우선 웅덩이 위치를 기록

- 맨 윗 줄과, 맨 왼쪽 줄은  웅덩이를 만나기 전까지는 다 1로 채운다.

- 어떤 좌표의 값은 그 좌표의 왼쪽 값과 위쪽 값을 더하여 구할 수 있다. 를 이용해서 (1,1) 부터 (n-1, m-1) 까지 값 구하기   

# 7분 : 런타임에러 
# 3분 : 실패
# 2분 : 10000007로 나눈 나머지라니 ... 근데 이건 영향 없네
# 10분 : -1먼저 처리해야하는 구나 
def solution(m, n, puddles):
    graph = [[0]*m for _ in range(n)]
    
    for i, j in puddles:
        graph[j-1][i-1] = -1
    
    for j in range(m):
        if graph[0][j] == -1:
            break
        graph[0][j] = 1
    
    for i in range(n):
        if graph[i][0] == -1:
            break
        graph[i][0] = 1
        
    # 둘 중 하나가 1인 경우 생각하기
    for i in range(1, n):
        for j in range(1, m):
            if graph[i][j] == -1:
                continue
            graph[i][j] = (0 if graph[i-1][j]==-1 else graph[i-1][j]) + (0 if graph[i][j-1]==-1 else graph[i][j-1])
            
    for row in graph:
        print(row)
        
    return (graph[n-1][m-1])%1000000007

 

 

---

[대표 풀이]

- 웅덩이가 있는 위치를 0으로 아예 기록해두면, 자연스럽게 0을 더하게 된다.

- -1 이었던 자리를 0으로 바꿔버려도 문제가 없다는 걸 생각을 못했다. 

def solution(m,n,puddles):
    grid = [[0]*(m+1) for i in range(n+1)] #왼쪽, 위로 한줄씩 만들어서 IndexError 방지
    if puddles != [[]]:                    #물이 잠긴 지역이 0일 수 있음
        for a, b in puddles:
            grid[b][a] = -1                #미리 -1로 체크
    grid[1][1] = 1
    for j in range(1,n+1):
        for k in range(1,m+1):
            if j == k == 1:                #(1,1)은 1로 만들어두고, 0이 되지 않도록
                continue
            if grid[j][k] == -1:           #웅덩이는 0으로 만들어 다음 덧셈 때 영향끼치지 않게
                grid[j][k] = 0
                continue
            grid[j][k] = (grid[j][k-1] + grid[j-1][k])%1000000007   #[a,b] = [a-1,b] + [a,b-1] 공식

    return grid[n][m]