1916_최소비용 구하기
https://www.acmicpc.net/problem/1916
N : 도시의 수
M : 버스의 수
입력 값 : N, M,
M개의 버스의 출발도시(u), 도착도시(v), 버스비용(cost),
출발지(A), 도착지(B)
출력 : A에서 B로 가는 경로의 최소비용
내가 생각한 해결법 1. dfs
이 문제를 보고 처음으로 떠올렸던 접근방법은 깊이우선탐색(dfs)였습니다.
A 정점에서 dfs탐색을 이용해 B 정점에 도착하는 모든 경우를 찾아서 그 중에 가장 적은 버스비용을 출력하는 방향으로 접근을 했습니다.
문제점 1. 시간복잡도
N(1 ≤ N ≤ 1,000)
M(1 ≤ M ≤ 100,000)
그래프의 모든 정점들이 서로 모두에게 갈 수 있는 정점들이 존재한다면,
시간복잡도는 N-2 개의 순열만큼이 걸리게 됩니다.
O((N-2)!) 이는 주어진 시간을 초과하게 되는 문제점이 발생합니다.
별도로 dfs 탐색 O(V + E)만큼의 시간이 필요하기도 합니다.
A - B - C - D - E
A - B - D - C - E
A - C - B - D - E
A - C - D - B - E
A - D - B - C - E
A - D - C - B - E
<모든 정점이 서로 직접적으로 연결되어있을 때 예시>
틀린 개선방법
왠만한 알고리즘 문제를 풀 때 시간초과가 날때마다 다이나믹 프로그래밍을 적용하면 시간복잡도를 줄일 수 있을것이라고 생각하여, 이 문제 또한 다이나믹 프로그래밍의 메모이제이션을 이용하면 시간복잡도를 개선시킬 수 있다 생각했습니다.
적용한 결과, 오답처리가 되었습니다.
long long dfs(int cur){
if(cur == B) return 0;
long long &ret = cache[cur];
if(ret != -1) return ret;
ret = INF;
for(int i = 0 ; i < connected[cur].size() ; i++){
int next = connected[cur][i].first;
int cost = connected[cur][i].second;
if(visited[next] == false){
visited[next] = true;
ret = min(ret, dfs(next) + cost);
visited[next] = false;
}
}
return ret;
}반례 : 첫 번째 경로가 무조건 memo에 저장됩니다.
A - B - C - D - E 이면 다음
A - B - D - C - E 를 계산할 때 이미 memo[B]가 정해져있는 것 입니다.
문제점 2. 부분문제 사이클
DP로 특정한 최적경로를 풀 수 없는 이유는 부분문제간의 사이클이 존재할 경우입니다.
최적경로 문제는 다음과 같이 나눌 수 있습니다.
간선치가 모두 일정할 경우 : 최적 == 가장 적은 간선 수를 필요로 하는 경로
간선치가 모두 다를 경우 : 최적 == 가장 간선치의 합이 적은 경로
이번 문제는 간선치가 모두 다르기 때문에
"x번 정점의 최단거리를 구하기 위해 y번 정점의 최단거리를 이용하는데,
y번 정점의 최단거리를 구하기 위해 x번 정점의 최단거리를 이용하는"
'부분문제 사이클'이 발생합니다.
올바른 개선방법
shortest path 알고리즘 중 하나인 dijkstra를 이용하면 문제를 해결할 수 있습니다.
참고자료
