[프로그래머스] 등굣길 [Java]

문제

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

---

풀이

MN크기의 보드에 장애물이 주어지고, (1, 1)에서 (M, N)까지 가는 최단 경로의 수를 1e9 + 7로 나눈 나머지를 출력하는 문제다.

보통 좌표가 NM으로 주어지지만 여기서는 MN이다. puddles가 가지는 좌표또한 MN임을 유의하자.

puddles에는 BLOCK표시를 해주자.

( 0, 1 ) 또는 ( 1, 0 )에 1을 기입해 (1, 1)이 1을 가질 수 있도록 해주자.

dp[i][j] : ( i, j )까지 오는 최단 경로의 수

이후에는 모든 경로를 탐색하며 장애물이 없는 칸이라면 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]을 통해 최단 경로의 수를 합쳐주자.

---

소스코드

보기