Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- 다익스트라
- 문제풀이
- baekjoon
- dp
- swea
- boot sequence
- Application Layer
- 응용 계층
- 네트워크
- 데이터베이스
- 릿코드
- DB
- Database
- Embedded
- 부트시퀀스
- C++
- 백준
- 관계형 모델
- Transport layer
- ps
- 자료구조
- BST
- STL
- 임베디드
- 전송 계층
- BHS
- Djikstra
- leetcode
- Network
- 프로그래머스
Archives
- Today
- Total
BOBO's Note
[ Baekjoon ] 10217. KCM Travel 본문
https://www.acmicpc.net/problem/10217
풀이 방법
소요시간을 기준으로 다익스트라 알고리즘을 적용해 풀 수 있다. 이때, 지원비용 내에서 최소 소요시간을 구하는 문제이기 때문에 한번 방문했던 vertex더라도 재방문할 수 있다(소요시간은 짧지만 비용이 커서 해당 경로로 못 갈 수 있기 때문이다).
처음엔 다익스트라 알고리즘에서 인접 vertex에 대해 distance 벡터를 업데이트해줄 때 다음과 같이 조건을 변형했었다. 이전에 방문한 적이 있는 vertex에 대해서는 distance 벡터를 업데이트해줄 수 없기 때문에 방문한 적이 있다면 무조건 재방문을 허용했는데, 이렇게 구현하니 우선순위 큐에서 메모리 초과가 발생했다.
for(auto e: adj[cur]){
if(dist[e.v] > dist[cur] + e.time || visit[e.v]){
dist[e.v] = dist[cur] + e.time;
pq.emplace(dist[e.v], total_cost + e.cost, e.v);
}
}
구글링을 통해 DP로 푸는 방법을 알아내었다. distance 벡터에 각 노드까지 도착하는 최소 시간을 업데이트 하는 게 아니라, 다음과 같이 각 노드까지 도착하는 비용에 대하여 최소 시간을 업데이트해나간다. 그 후, 도착 지점에서 비용에 상관없이(무조건 지원비용 범위 내의 비용이다) 최소 시간을 반환한다.
// min_time[i][j]: 노드 i까지 j원으로 도착하는 최소 시간
int min_time[N+1][budget+1];
// update distance vector
for(auto e: adj[cur]){
int c = total_cost + e.cost;
if(c <= budget){
if(min_time[e.v][c] > min_time[cur][total_cost] + e.time){
min_time[e.v][c] = min_time[cur][total_cost] + e.time;
pq.emplace(min_time[e.v][c], c, next);
}
}
}
전체 코드는 여기서 확인할 수 있다.
'Algorithm > Problem Solving' 카테고리의 다른 글
[ Baekjoon ] 17837. 새로운 게임2 (0) | 2020.05.31 |
---|---|
[ Baekjoon ] 5373. 큐빙 (0) | 2020.05.31 |
[ Baekjoon ] 1753. 최단 거리 (0) | 2020.05.27 |
[ Baekjoon ] 3190. 뱀 (1) | 2020.05.23 |
[ Baekjoon ] 17140. 이차원 배열과 연산 (0) | 2020.05.23 |
Comments