취준/프로그래머스
[프로그래머스 Programmers][Python] 등굣길
puff
2020. 1. 24. 18:18
문제 : https://programmers.co.kr/learn/courses/30/lessons/42898
코딩테스트 연습 - 등굣길 | 프로그래머스
계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다. 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다. 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매
programmers.co.kr
이 문제는 DP에서 전형적으로 나오는 최단경로 문제이다.
복잡한 조건이 없는 최단경로 개수는 방식이 정해져 있다.
- 우선 최단경로로 갈 수 있는 방법을 생각한다.
- 이 문제의 경우 오른쪽, 아래 2가지 경우뿐이다.
- d[i][j] = (d[i-1][j] + d[i][j-1])
- 각 길에 대한 가중치 같은 것이 있나 확인한다.
- 이 문제는 없다. 있을 시 max 등을 확인해서 계산할 것
- 맵에 대한 초기화를 실행한다.
- 길 찾기 문제 중에 d[1][i] = sth 이 값을 초기 설정해줘야 하는 경우가 있다.
- 지금은 아님.
- 못 가는 길을 확인한다.
- 이 경우는 puddles 잠긴 지역이 있으니, for 문을 돌며 갈 수 없는 길일 경우 0 처리한다.
- if ~else 구문이 조건 처리 코드이다.
def solution(m, n, puddles):
answer = 0
d = [[0]*(m+1) for _ in range(n+1)]
d[1][0] = 1
for i in range(1,n+1):
for j in range(1,m+1):
if [j,i] in puddles:
d[i][j] = 0
else:
d[i][j] = (d[i-1][j]+d[i][j-1])%1000000007
return d[n][m]