Algorithms / Programmers / 등굣길

링크

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

풀이

• 좌표평면상의 점 x and y는 배열상의 index가 아니므로 -1 처리.
• 2중 반복문에서의 변수 i and j는 좌표평면상의 점x and y와 위치가 뒤바뀜.
• distance[i][j]번째 배열의 최단거리 = 윗칸의 최단거리 + 왼쪽칸의 최단거리
  • = distance[i][j] = distance[i-1][j] + distance[i][j-1]

코드

def solution(m, n, puddles):
    answer = 0
    maps = [[1]*m for _ in range(n)]
    distance = [[0]*m for _ in range(n)]
    for item in puddles:
        x, y = map(int, item)
        maps[y-1][x-1] = 0
    distance[0][0] = 1
    for i in range(n):
        for j in range(m):
	        # meeting puddle
            if maps[i][j]==0:
                continue
            elif maps[i][j]==1 and distance[i][j]==0:
                distance[i][j]=distance[i-1][j]+distance[i][j-1]
    answer = distance[-1][-1] % 1000000007
    return answer