[백준 / BOJ] 10164 격자상의 경로

문제

출처 : www.acmicpc.net/problem/10164

10164번: 격자상의 경로

N*M 그리드에서 무조건 (1,1) 에서 시작하여 (Y,X)지점을 지나 (N,M)지점에 최소한의 이동으로 도달하는 경로의 수를 구하는 문제다.

 

풀이

dp로 풀리는 문제였다.

 

전 지점에 최소로 도달하는 경로의 수를 알고있다면, 현재위치까지 오는 경로의 수를 알수있다.

 

예제처럼

3*5 그리드가 있다고 가정해보자

 

0 0 0 0 0 

0 0 0 0 0

0 0 0 0 0

 

우선, Y = 1인 부분과 X=1인부분은 직선으로 가는 경우가 최소이므로 항상 1이다.

 

1 1 1 1 1 

1 0 0 0 0

1 0 0 0 0

 

Y = 2, X = 2 인 부분부터 연산을 시작해줘야하는데, 

(Y = 2, X = 2)인 지점을 보면, 위에서 내려오는 경우 와 왼쪽에서 오는경우 2가지밖에없다.

 

1 1 1 1 1 

1 2 0 0 0

1 0 0 0 0

 

Y = 2 , X = 3 인 지점을 보면, 옆에서 오는경우와 위에서 내려오는 경우가 최소값이다.

이때, 왼쪽에 도달하는 최소경로의 수가 2개이므로,

Y = 2, X = 3 지점은 2 + 1 이 되서 3이된다.

즉, 해당 (Y,X)까지의 최솟값은 (Y-1,X)지점까지 도달하는 최솟값 + (Y,X-1)지점까지 도달하는 최솟값이 된다.

(옆에서 바로 한칸 이동하는 경우는 항상 1가지이므로.. )

 

따라서 DP식은 dp[y][x] = dp[y-1][x] + dp[y][x-1]; 이 된다.

 

이런식으로 채워나가면되는데, 이때, 무조건 K번째 지점을 지나가야한다는 조건이있으므로, 1,1에서 바로 N,M지점을 가주는게아닌,

1,1에서 K번째 지점을 가주고나온값에 K번째지점부터 N,M지점을 가준 경우의수를 곱하면 답이다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/10164%20%EA%B2%A9%EC%9E%90%EC%83%81%EC%9D%98%20%EA%B2%BD%EB%A1%9C/main.cpp

devxb/JJUNalgo