💡 문제 해결 아이디어

내가 생각한 아이디어

• 중고등학교 때 풀던 수학 문제를 생각하면 쉽게 풀 수 있다고 생각한다.
• 해당 좌표로 오는 최단 경로의 수는 "왼쪽에서 오는 경로" + "위에서 오는 경로"이다.
• 그렇다면 맨 윗줄(또는 맨 왼쪽줄)부터 순차적으로 한 줄씩 계산한다면, 큰 어려움 없이 문제를 풀 수 있다.

주의할 점 - 좌표평면에서 (x, y)는 2차원 배열에서 Array[y][x]로 조회 해야 한다.

💻 작성된 코드

def calc(x, y, matrix):
	# 벗어난 좌표의 경로는 0을 반환
    if x < 0 or y < 0:
        return 0
    return matrix[y][x]

def solution(m, n, puddles):
	# 모든 위치를 1로 초기화
    matrix = [[1] * m for _ in range(n)]
    
    # 물에 잠긴 지역을 0으로 변경, index를 고려해 -1 연산
    for puddle in puddles:
        matrix[puddle[1]-1][puddle[0]-1] = 0
        
 	# 맨 왼쪽줄부터
    for x in range(m):
    	# 위에서  아래로
        for y in range(n):
        	# 만약 물에 잠겼거나 첫 시작지점이라면, 계산 없이 continue
            if matrix[y][x] == 0 or (x == 0 and y == 0):
                continue
            # 아니라면, 왼쪽에서 오는 경로 + 위에서 오는 경로를 계산
            matrix[y][x] = calc(x-1, y, matrix) + calc(x, y-1, matrix)
            
    return matrix[y][x] % 1000000007