[프로그래머스][Python] 등굣길
문제를 정리해보자. m x n 크기의 격자 모양이 있다. (1, 1)에는 집이 있고, (m, n)에는 학교가 있다. 일부 칸은 물에 잠겨 있다. 물에 잠긴 칸은 지나갈 수 없다. 집에서 학교까지 갈 수 있는 최단 경로의 개수를 구하자. 단, 이동은 오른쪽과 아래쪽만 가능하다. 풀이를 생각해보자. 이동은 무조건 오른쪽과 아래쪽으로만 가능하다. 따라서 어떻게 가도 최단 경로이다. 오른쪽 그림을 보자. 각 좌표까지의 최단 경로를 나타냈다. 마지막 (m-1, n-1)는 위에서 2가지, 왼쪽에서 2가지로 경로가 총 4가지이다. ((0, 0)이 시작이라고 잡았기 때문에 도착은 (m-1, n-1)이다.) 구현해보자. BFS를 이용해서 (0, 0)부터 인접한 좌표로 이동하게 했다. 다만, check리스트를 이용해서 방..
