23.03.07 파이썬 코딩 퀴즈#186 등굣길(프로그래머스 스쿨)

이번 문제는 등굣길 문제이다.

전달받은 2차원 배열 puddles 을 확인하여, 집에서 학교까지 가는 최단 경로의 개수를 1,000,000,007로 나눈 나머지를 return 하는 문제이다. 위 그림에서는 설명이 하나가 빠졌다.

다시 그림을 보자. 우물이 있는걸 볼 수 있다.

즉 우물이 잠긴 지역을 피해, 오른쪽과 아래쪽으로만 이동하여 진행해야 하고, 이때의 최단경로를 찾아야 한다.

 

집은 언제나 (1,1)에 위치하고, 학교는 언제나 배열의 가장 우측 하단에 위치한다.

그리고 문제에서는 최단경로라고 얘기했지만, 해당 문제에서는 돌아가는 선택지는 존재하지 않는다. 또한 이동방향은 오른쪽과 아래쪽으로만 움직인다. 따라서 우물을 만나는 경로가 아니라면 모든 경로의 길이는 같다. 

 

단순하게 미로찾기로 생각하고 코드를 짜보자.

굉장히 자주 등장하는 코드이기에 설명은 생략한다.

정확성에서 한문제 시간초과, 효율성 전부 시간초과이다.

이제 다시 위 예제를 기준으로 가는 방법에 대해 생각해보자.

우물이 없는 경우라면 위 그림과 같이 총 10개의 길이 존재한다.

하지만 우물에 의해 총 6개의 길이 가려졌으며, 이로 인해 갈 수 있는 방법은 총 4가지가 된다.

 

이를 역으로 생각해보면 학교의 왼쪽길로 들어오는 경우와 위쪽길로 들어오는 경우로 또 나누어 진다.

작은것 부터 생각해보자, 먼저 2x2 배열 기준이다.

시작점 (1,1)에서 갈수 있는 방향을 나열해보면 왼쪽과 같고, 

도착점(2,2)를 기준으로 들어오는 방향을 계산해보면 오른쪽과 같다.

즉 도착지점까지의 경우의 수는 위쪽 과 왼쪽의 가지수의 합이 된다.

3x3 기준으로 보면 규칙이 더 명확하게 보인다.

도착지점으로 가는 경우의 수는 왼쪽 도착의 경우의 수 + 오른쪽 도착의 경우의 수와 같다. 

 

이제 코드로 작성해 보자.

설명에 비해 코드는 간단하다.

먼저 m 또는 n 이 1인, 즉 길이 한개뿐인 경우라면 바로 answer 를 반환하여 예외처리를 해주었다.

(사실 코드 특성상 예외처리를 안해도 문제는 없다.

dp 는 0으로 가득 채워진 2차원 배열을 준비하였고, 시작점은 1로 전달해 주었다.

이제 i,j 는 각 행,열의 index 1부터 돌면서 값을 더해나가기 시작한다.

당연히 (1,1)은 이미 값이 존재하고, 우물은 계산을 건너띄어야 하기에 조건문으로 처리하였다.

그 외의 경우 2차원 배열기준 현재 좌표의 왼쪽과 위쪽의 값을 합하여 전달하였다.

그리고 최종적으로 구해야할 값은 배열읜 (m,n) 이기에 dp[-1][-1] 을 100,000,007로 나눈 나머지를 반환하면 된다.