Programmers - 등굣길[파이썬(python)]

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

 

입출력 예

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

 

입출력 예 설명

 

---

문제 풀이

오른쪽과 아래쪽으로만 움직일 수 있으므로 어떤 경로로 가던 학교에 도달했을 때 그 경로는 최단 경로가 되므로 2차원 DP 테이블에 해당 지역에 도달할 수 있는 모든 경우의 수를 더해주면 된다. 이때 x좌표가 0인 지역과 y좌표가 0인 지역은 오른쪽과 아래쪽으로만 움직일 수 있으므로 전부 한 가지 경우밖에 존재하지 않는다. 그 외의 나머지 지역은 해당 지역의 왼쪽에서 온 경로의 수와 위쪽 지역에서 온 경로의 수를 더해줌으로써 구할 수 있다. 이과정을 BFS를 통해 DP 테이블을 학교 위치까지 갱신하면 학교까지 도달할 수 있는 모든 경로의 수를 구한 것이 답이 된다.

구현 코드

코드 링크 : 등굣길

 

from collections import deque

def solution(m, n, puddles):
    dx = [1, 0]
    dy = [0, 1]
    graph = [[0]*m for _ in range(n)]
    graph[0][0] = 1
    
    def bfs():
        q = deque([[0, 0]])
        while q:
            x, y = q.popleft()
            for i in range(2):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx<n and ny<m and [ny+1,nx+1] not in puddles:
                    if graph[nx][ny]==0:
                        if nx == 0:
                            graph[nx][ny] = graph[nx][ny-1]
                            q.append([nx,ny])
                        elif ny == 0:
                            graph[nx][ny] = graph[nx-1][ny]
                            q.append([nx,ny])
                        else:
                            graph[nx][ny] = graph[nx-1][ny] + graph[nx][ny-1]
                            q.append([nx,ny])
    
    bfs()
    return int(graph[-1][-1]%1000000007)