[코딩 테스트] 프로그래머스 - 등굣길 (Lv.3) in Python

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

 

예시: m = 4, n = 3, puddles = [[2, 2]]  ~> answer = 4

정답은 4이다

 

더 자세한 설명

- programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길

 

풀이

- 고등학교 때 풀어본 듯한 문제이다...

- 동적계획법 대부분의 풀이처럼, 각 좌표에 그 좌표에 이를 수 있는 길의 수를 저장하면 된다.

비슷한 문제 참고 - 땅따먹기 

- 예를 들면, 집이 있는 (0,0) 좌표에는 갈 수 있는 길이 하나다.

  첫 행에 해당하는 좌표들도, 첫 열에 해당하는 좌표들도, 오른쪽 혹은 아래로 갈 수 있는 방법 뿐이라고 문제에서 규정했으니, 도달할 수 있는 방법의 수는 1이다.

- 두 번째 행, 네 번째 열의 좌표까지 갈 수 있는 방법은, 위 좌표의 값 (1) + 왼쪽 좌표의 값 (1) = 2 가 된다.

- 물 웅덩이가 있는 곳은 갈 수 없으므로, puddle이 위치하면 0으로 만들어준다.

 

 

 

파이썬 코드 구현!

 

def solution(m, n, puddles):    
    #initialization    
    paths = [[0] * m for _ in range (n)]     

    # count # of possible paths to reach each coord
    for i in range(n):
        for j in range (m):
            # 집의 위치에 해당하는 좌표
            if (i,j) == (0,0):
                paths[i][j] = 1
            # j, i가 바뀌었음을 주의
            elif [j+1,i+1] in puddles:
                paths[i][j] = 0
            else:
                paths[i][j] = paths[i-1][j]+paths[i][j-1]
            
    
    return paths[n-1][m-1] %1000000007

 

- puddles에 있는 좌표가 [열, 행]으로 주어지는 점이 헷갈려서 애를 먹게 했다. 문제를 잘 읽을 것.

- else: 부분이 흥미로운데, 첫번째 열과 첫번째 행은 [i-1] 혹은 [j-1]이 [-1]이 되어 오류를 일으킬 법도 하지만, 처음 초기화를 모두 0으로 시켜줬기 때문에 괜찮다. [-1]인덱스가 되어 반대편 끝의 열/행을 참조하여도 0을 얻기 때문이다.