Programmers / 등굣길 / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 등굣길 (3단계) - 동적 계획법

문제 사이트: 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개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

입출력 예mnpuddlesreturn

4

3

[[2, 2]]

4

입출력 예 설명

---

이 문제는 정수 삼각형 문제와 비슷한데, 물 웅덩이라는 제약조건을 추가한 동적 계획법 문제이다.

 

최단 경로 찾기 문제는 고등학교 수학 시간에 배운 것 같다 (확률과 통계 시간 인가..)

 

먼저 map을 만들어 좌표를 구현할 수 있게 한다. 그리고 물 웅덩이가 없는 첫번째 행과 첫번째 열에 1을 적어주고 

(0,0) 좌표 기준으로 (1,1) 행에서 (1,1)도 물웅덩이를 지나지 않으면 (0,1)과 (1,0)의 값들을 더해 넣어주면 된다. 그렇게 각 행들을 순회하며 값을 더해나가면 최종적으로 목적지에는 해당 경로를 지나온 가짓수가 출력된다.

여기서 '물웅덩이' 라는 제약 조건이 좀 까다로운데, 일단 이동할 수 있는 방향은 오른쪽과 아래쪽으로만 가능하다.

 

그리고 물웅덩이의 좌표가 [x,y] 순서가 아니라 [y,x]라는 점을 잘 알아야한다. -> 문제에서 제대로 설명 안되어있는 것 같다;;

나의 풀이 (첫번째 풀이 - 75점)

def solution(m, n, puddles):
    # 오른쪽과 아래쪽으로만 움직여야함
    # 최단 경로의 개수를 리턴

    maps = [[0 for i in range(m)] for j in range(n)]
    
    for row in range(1,n): # 행
        if [1,row + 1] not in puddles:
            maps[row][0] = 1
    
            
    for cal in range(1,m): # 열
        if [cal +1,1] not in puddles:
            maps[0][cal] = 1

        
    for i in range(1,n):
        for j in range(1,m):
            if [j+1,i+1] not in puddles:
                maps[i][j] += maps[i-1][j] + maps[i][j-1]

    return maps[-1][-1] % 1000000007

 

여기서 문제가 통과 안된 이유는 이동할 수 있는 방향은 오른쪽과 아래쪽으로만 가능 하다는 점에서이다.

 

첫번째 행과 첫번째 열에 1을 적어주고 (0,0) 좌표 기준으로 (1,1) 행에서 (1,1)도 물웅덩이를 지나지 않으면 (0,1)과 (1,0)의 값들을 더해 넣어주면 되는데,

 

일단 물 웅덩이를 첫번째 행이나 첫번째 열에서 보게 된다면 해당 방향쪽으로는 전혀 갈 수 없다.

따라서 1을 그려주다가 이동할 수 없으므로 해당 방향은 break를 걸야한다.

 

나의 풀이 ( 두번째 풀이 - 통과 )

def solution(m, n, puddles):
    # 오른쪽과 아래쪽으로만 움직여야함
    # 최단 경로의 개수를 리턴

    maps = [[0 for i in range(m)] for j in range(n)]
    
    for row in range(1,n): # 행
        if [1,row + 1] not in puddles:
            maps[row][0] = 1
        else:
            break
    
            
    for cal in range(1,m): # 열
        if [cal +1,1] not in puddles:
            maps[0][cal] = 1
        else:
            break
        
    for i in range(1,n):
        for j in range(1,m):
            if [j+1,i+1] not in puddles:
                maps[i][j] += maps[i-1][j] + maps[i][j-1]

    return maps[-1][-1] % 1000000007

 

---

※ 알아야 할 것

- 좌표에 이전 값들을 더해가는 메모이제이션!!