[알고리즘] Programmers 등굣길 #Python

[Programmers] 등굣길 바로가기

📍 문제 설명

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

---

📍 입출력 예

m	n	puddles	return
4	3	[[2, 2]]	4

---

📍 입출력 예 설명

---

📍 문제 풀이

• 집이 있는 위치(1, 1) 에서 학교가 있는 위치(m, n) 까지 이동하기 위한 최단거리 방법은 현재 위치에서 우측 이동, 하단 이동 밖에 없다.
• 이동 방법이 우측 이동 및 하단 이동 밖에 없다는 것은 현재 위치(x, y)로 올 수 있는 방법이 x-1, y 혹은 x, y-1 에서 진입하는 방법밖에 없다.
• 정리하면 현재 위치로 올 수 있는 경로의 수는 현재 위치의 좌측과 상단측의 경로의 수를 더한 것과 같다.
• 방정식으로 표현하면 graph[y][x] = graph[y-1][x] + graph[y][x-1] 과 같다고 볼 수 있다.

• 0 으로 이루어진 (m+1) * (n+1) 크기의 graph 를 생성한다.
  • graph[1][1] = 1 의 의미는 집이 위치한 곳을 의미한다.
• 주어진 puddles 의 값을 통해 물웅덩이가 존재하는 위치에 X 의 값을 담는다.
• 1행부터 n 행까지 1열부터 m 열까지 순차적으로 진행한다.
  • 현재 위치가 물웅덩이(puddle)의 위치라면 continue 를 통해 다음 반복문을 수행한다.
  • 현재 위치의 좌측이 물웅덩이라면 좌측을 통해 이동할 수 있는 경로가 없다는 것을 의미한다.
  • 현재 위치의 상단측이 물웅덩이라면 상단측을 통해 이동할 수 있는 경로가 없다는 것을 의미한다.
    • 위의 경우가 아닌경우에만 좌측과 상단측의 경로의 수를 현재 위치의 값에 더한다.
  • 현재 위치의 최단 경로의 수를 구한 후 1000000007로 나눈 나머지값으로 갱신한다.
• 반복문이 종료된 후 graph 의 학교 위치(m, n)에 해당하는 값을 반환한다.

✍ 코드

def solution(m, n, puddles):
    answer = 0
    graph = [[0] * (m+1) for _ in range(n+1)]
    graph[1][1] = 1
    
    for puddle in puddles:
        graph[puddle[1]][puddle[0]] = 'X'
        
    for y in range(1,n+1):
        for x in range(1,m+1):
            if graph[y][x] == 'X': continue
            if graph[y][x-1] != 'X': graph[y][x] += graph[y][x-1]
            if graph[y-1][x] != 'X': graph[y][x] += graph[y-1][x]
            graph[y][x] %= 1000000007
            
    return graph[n][m]