프로그래머스 [등굣길]

문제

문제 보기

다음 그림과 같이 board 가 주어진다. 물웅덩이는 지나갈 수 없다.

집에서 학교까지 아래, 오른쪽으로만 움직여서 갈 수 있는

최단경로의 개수를 구하는 문제이다.

풀이

for문을 두 개돌려서 모든 칸을 순서대로 탐색하고 각 칸에는

그 칸까지 가는 경로가 저장된다.

(오른쪽, 아래쪽 으로만 움직일 수 있으므로 가는 경로가 모두 최솟값이다.)

NC SOFT에서 DP로 풀어야 하는 문제를 백 트랙킹으로 풀고 나서

충격받아 DP 문제를 풀었다.

다음 조건을 읽지못하여 BFS로 풀려다가 아닌 것 같아풀이를 보았다...

X == 0 or Y == 0 인 칸은 가는 방법이 모두 1가지이다.

단, 중간에 물웅덩이가 있으면 물웅덩이 부터 끝까지는 갈 수 있는 방법이 없다.

for문을 두 개돌려서 모든 칸을 순서대로 탐색하고 각 칸에는

그 칸까지 가는 경로가 저장된다.

(오른쪽, 아래쪽 으로만 움직일 수 있으므로 가는 경로가 모두 최솟값이다.)

X == 0 or Y == 0 인 칸은 위에서 말한대로 설정해준다.

나머지는 윗쪽과 왼쪽칸 중 웅덩이가 아닌칸의 경로수를 더해준다.

이렇게 끝까지 진행하고 마지막칸에 적힌 값을 return 해주면 된다.