(JAVA) 백준 10217번 : KCM Travel --- [다익스트라, DP]

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

10217번: KCM Travel

 

안녕하세요.

 

단일 노드 -> 단일 노드 의 최단 경로(시간)를 구하는 문제이기 때문에,

 

다익스트라와 DP를 사용했습니다.

 

왜 다익스트라와 DP를 사용해야 하느냐?

 

 

https://dragon-h.tistory.com/26?category=789780

위의 포스팅을 참고해서 이유를 적어봤습니다.

 

--------------------------------------------------------------------------------------------------------

문제 유형 - 일정 비용 내로 이동하는 최단 시간(경로) 구하기

 

가중치가 1이 아니므로 DFS, BFS가 아닌 다익스트라, 벨만 포드, 플로이드 와샬을 사용해야 한다.

  *** 가중치가 1로 같으면 : DFS, BFS

  *** 가중치가 1이 아니고 각기 다르면 : 다익스트라, 벨만 포드, 플로이드 와샬

 

한 노드 ▶ 노드 이므로 다익스트라, 벨만 포드를 사용해야 한다.

 

음의 가중치는 없기 때문에 다익스트라를 사용해야 한다.

  *** 벨만 포드의 시간복잡도 : O(VE) / O(E ^ 2) // V : Vertex, E : Edge

  *** 다익스트라의 시간복잡도 : O(V^2) 에서 우선순위 큐 사용하면 O(ElogV) 가 됨.

  *** 진행 속도 : 벨만 포드 <<< 다익스트라

--------------------------------------------------------------------------------------------------------

 

다익스트라를 통해 시작 지점부터 끝 지점까지 이동하는데 걸리는 최단 시간을 알 수 있고,

 

DP 2차원 배열을 통해 해당 지점까지 이동하는데 사용한 비용 및 시간 을 파악할 수 있습니다.

 

 

DP[i][j] = 시작 공항부터 i 공항까지 j의 비용을 소비하며 이동한 시간 중 최소 시간 

 

 

그럼, DP의 크기는 DP[공항의 수][최대 지원 비용] 이 되겠죠?

 

 

이후는 간단합니다.

 

다익스트라 알고리즘을 사용해 DP[n][0] ~ DP[n][m] 중 가장 작은 값을 구하면 끝!

 

 

가장 작은 값을 구하는 이유는

 

이미 M원 이내를 충족했기 때문에, M원 이내로 이동한 경우 중 최단 시간을 찾아내야 하기 때문입니다.

 

 

 

추가로, 소스코드 중 메모리 효율 + 속도 감소를 위한 코드가 있습니다.

// 이미 해당 금액으로 해당 번 공항으로 왔을 때의 최소 시간보다 크면 업데이트할 의미가 없다. 
if(moneyDp[nextNum][nextMoney] <= nextTime) {	
	continue;
}

// 불필요한 삽입 방지를 위해 그 이상의 모든 값에 현재 최단시간 값을 설정해준다.
// 그래야 위 조건에 부합해서 continue 떠서 넘어가지.
for(int j = nextMoney; j <= m; j++){
  if(moneyDp[nextNum][j] > nextTime) {
  	moneyDp[nextNum][j] = nextTime;
  }
}

바로 이 부분인데, 예를들어

 

 

2번 공항까지 오는데 100원을 소비했고, 10초가 걸렸다.

 

라고 할 때, 다익스트라 진행 중 또다시

 

2번 공항까지 오는데 100원을 소비했고, 20초가 걸렸다.

 

를 얻었을 때, 당연히 10초가 걸린 이전 값을 사용해야 시간이 덜 걸릴 가능성이 높겠죠?

그래서 이런 일이 있으면 그냥 continue로 빨리빨리 건너뜁니다.

 

 

다음으로,

 

 

2번 공항까지 오는데 10원을 소비했고, 10초가 걸렸다.

 

2번 공항까지 오는데 50원을 소비했고, 20초가 걸렸다.

 

2번 공항까지 오는데 80원을 소비했고, 15초가 걸렸다.

 

2번 공항까지 오는데 100원을 소비했고, 25초가 걸렸다.

 

 

가 있다면, 당연히 가장 처음 값을 사용하는 것이 맞습니다. 최소 시간이니까.

그럼 나머지 배열의 값들을 그대로 둘 것이냐? 하는 문제입니다.

 

 

 

왜 이런 고민을 하냐면

 

어차피 "2번 공항까지 오는데 10원, 10초를 사용하는 것이 최적" 이란 결과를 얻었어서,

 

2번 공항까지 오는데 20원, 15초든 20원, 150초든 10초보다 작지 않으면 이 값(DP[2][20]) 을 바꿔도 의미가 없기 때문입니다.

 

그래서 최적의 시간이라고 판단했을 때, 소모되는 비용보다 큰 애들을 전부 같은 시간이 걸렸다고 설정합니다.

 

 

 

위 내용을 참고하시면, 바로 해결하실 수 있습니다.

모르거나 궁금한 부분은 아래 소스코드 및 주석을 참고해주세요!

 

 

감사합니다.

 

 

소스코드

---