[백준] No.10251 - 운전 면허 시험 (C++, DP)

문제

 

https://www.acmicpc.net/problem/10251

10251번: 운전 면허 시험

 

풀이

 

solved.ac 난이도: Gold 1

 

 

참조 풀이

JusticeHui님의 백준10251 운전 면허 시험 풀이

 

 

언뜻 보면 최단 거리를 구하는 문제 같지만 사용할 수 있는 연료의 한계가 있기 때문에 풀기 어려웠던 문제.

연료에 제한이 있으면 해당 경로가 최단 경로이라도 연료의 사용량이 많다면 결국에 이용을 못 할 수 있으므로 모든 경우의 수를 생각해보아야 한다.

 

이때 중요한 것이 모든 도로를 지나는데 걸리는 시간은 L로 동일하고, 방향을 전환할 때만 추가적으로 +1 시간이 소모된다.

시작점에서 목적지까지 아래와 오른쪽으로만 이동해서 지나는 도로의 개수는 모든 경로가

Row -1(세로 방향의 이동 횟수) + Column -1(가로 방향의 이동 횟수)로 동일하다.

따라서 최종적으로 소요되는 시간은 방향 전환의 횟수(turn)에만 영향을 받는다.

 

 

(r,c)좌표에서 방향 전환은 다음 두 가지에 의해 결정된다.

1.  (r,c)좌표로 들어온 방향

2.  다음 좌표로 나가는 방향

 

만약 1과 2가 같다면 방향 전환을 일어나지 않는다.

하지만 1과 2가 다르다면 방향 전환이 일어난다.

 

이를 이용해서 4차원 dp를 적용하여 문제를 해결해보자.

dp[r][c][turn][dir]는 다음과 같이 정의된다.

dp[r][c][turn][dir] : turn번 방향 전환하여 (r,c) 좌표에 dir방향으로 도달했을 때의 최소 연료량

(오른쪽을 dir: 0, 아래쪽을 dir: 1라고 하자.)

 

좌표 (r,c)에서 발생할 수 있는 경우는 4가지가 존재한다.

 

 

 

1. 아래로 (r,c)에 진입하여 오른쪽(r, c+1)으로 나간다.

이때의 비용(연료 소모량)은 아래로 (r,c)에 진입한 값인 dp[r][c][turn][0]에 방향을 오른쪽으로 전환하여 (r,c+1)로 나가는 비용 right_cost[r][c]을 더한 값이다.

dp[r][c+1][turn+1][0] = dp[r][c][turn][1] + right_cost[r][c]

방향이 전환되었으므로 다음 좌표에는 turn + 1의 전환 횟수로 도달한다.

 

 

2. 오른쪽으로 (r,c)에 진입하여 오른쪽(r, c+1)으로 나간다

 

방향 전환이 없이 오른쪽으로만 이동하므로 전환 횟수 turn은 증가하지 않고 (r, c+1)에 도달한다.

dp[r][c+1][turn][0] = dp[r][c][turn][0] + right_cost[r][c]

 

 

3. 아래쪽으로 (r,c)에 진입하여 아래쪽(r+1, c)으로 나간다

 

 

방향전환이 없이 아래쪽으로만 이동하므로 전환횟수 turn은 증가하지 않고 (r+1, c)에 도달한다.

dp[r+1][c][turn][1] = dp[r][c][turn][1] + down_cost[r][c]

 

 

4. 오른쪽으로 (r,c)에 진입하여 아래쪽(r+1, c)으로 나간다

 

방향전환으로 (r+1,c)에 도달한다.

dp[r+1][c][turn+1][1] =  dp[r][c][turn][0] + down_cost[r][c]

 

 

 

이러한 4가지 경우를 모든 좌표에서 가능한 방향 전환 횟수에서의 dp값을 구해주면 된다.

만약 해당 전환 횟수에 좌표에 도달할 수 없는 경우라면 dp의 최기화 값인 INF값으로 계산되어 정답에는 영향을 미치지 않는다.

 

 

 

코드