[Programmers] 등굣길 Solution (Python)

문제 원문 링크 : https://programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길

Dynamic Programming 카테고리에 있는 문제다.

얼핏 보면 굉장히 쉬워보이고 금방 풀릴 것 같은데, 은근히 생각지도 못한 곳에서 발목을 잡혔다.

 

문제에서 집이 왼쪽 상단, 학교가 오른쪽 하단에 위치하기 때문에, 학생은 오른쪽 또는 아래쪽으로만 이동한다고 생각하면 된다.

왼쪽이나 위쪽으로 도중에 움직이게 된다면 최단 경로가 아닐 것이다.

 

이제 2차원 행렬을 생성하고, 모든 점들을 순회하며 그 점을 지나는 최단 경로들의 개수를 하나씩 구해나가면 된다.

(이때 2차원 행렬 원소들의 초기화는 모두 0으로 한다)

 

여기서 최단 경로를 계산하는 방법을 크게 3가지로 나눌 수 있는데, 이는 아래와 같다.

(구현 편의 상 지도 상의 점들의 기준을 (1, 1)이 아닌 (0, 0)에 두자.)

 

(0, y)	(0, y-1)를 지나는 최단 경로 수
(x, 0)	(x-1, 0)을 지나는 최단 경로 수
(x, y)	(x-1, y)를 지나는 최단 경로 수 + (x, y-1)을 지나는 최단 경로 수

* x는 (m-1) 이하의 자연수, y는 (n-1) 이하의 자연수

---

처음에 헷갈렸던 부분 : (0, y), (x, 0)에 해당하는 원소를 모두 1로 초기화해도 되는가?

 

이는 간단한 예시를 들어서 생각해보니 바로 안 된다는 결론을 얻을 수 있었다.

 

집	물웅덩이
물웅덩이
		학교

 

이 경우 (0, y), (x, 0)에 해당하는 원소를 모두 1로 초기화해버린다면, 원래는 0이 들어갔어야 할 (0, 2), (2, 0)의 원소에 1이 들어가는 모순이 생긴다.

 

이때 각각의 경우, 이전의 (0, y-1), (x-1, 0)의 원소 값을 넣으면 이 문제를 해결할 수 있다.

---

그런데 1,000,000,007으로 나눈 나머지를 return하라는 조건은 왜 있는 것일까?

 

이 조건을 제대로 고려하지 않고 제출을 하면, 정확도는 100점인데, 효율성에서 0점을 받는다.

 

(0, 0), (0, y), (x, 0)의 경우는 0 아니면 1의 값 밖에 갖질 못한다.

그러나 (x, y)의 경우는 m = 100, n = 100일 때 매우 큰 값을 갖는 경우도 생긴다.

그리고 이렇게 큰 값을 가지고 연산을 하려고 하니 시간이 오래 걸리게 된다. (정확한 이유 아시는 분 댓글 고고)

 

따라서 (x, y)의 경우엔 (x-1, y)와 (x, y-1)의 원소 합을 1,000,000,007으로 나눈 나머지를 넣어주면 된다.

 

연산이 다 끝난 뒤엔 (m-1, n-1) 원소를 return하면 끝!

 

* 2차원 행렬을 구현을 위해 numpy 라이브러리를 사용했습니다.

---

Code

https://github.com/changyeon2/Algorithm/blob/master/programmers/%EB%93%B1%EA%B5%A3%EA%B8%B8/python3/solution%201.py