Approach 잘 생각해보면, 도착 높이에 대한 가치는 이미 고정되어 있는 상황이므로 해당 장소까지 방문하는데 소모된 체력을 최소한으로 만들기 위한 경로를 찾는 문제로 바뀐다. 추가적으로 소모된 체력은 이동 거리와 비례하는 상황이므로, 문제 상황은 최단 거리를 구하는 문제로 바뀌게 된다. 따라서 해당 지점에서 다익스트라 문제임을 쉽게 파악할 수 있다. 문제 조건에서 고려해야할 점은 다음과 같다. 1. 목표지점 도착 전까지는 높이가 올라가는 방향일떄만 dist 갱신이 가능하다. 2. 출발점과 목표지점, 목표지점과 고려대학교까지 도달하는 경로가 존재하지 않을 수 있다. 만약 한 경우라도 없다면 계산에서 제외시켜주어야 한다. 이를 위하여 다익스트라 기준점을 출발점과 고려대학교로 잡으면 된다. (고려대학교로 ..

Approach 다익스트라에 parent 배열을 활용해주면 쉽게 풀 수 있다. 다익스트라를 돌면서 갱신될 때마다 parent[to] = cur를 수행해주고, 역으로 출발점이 될 때 까지 계속해서 역으로 타고가면 경로를 추적할 수 있다. 약간 DP 역추적 같은 느낌으로 이해하면 충분하다. Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long ll; typedef pair pii; int move_x[4] = {-1, 1, 0, 0}; int move_y[4] = {0, 0, -1, 1}; int INF = 20000; int main() { fastio; int n, m; cin >>..

Approach 최단 시간을 찾는 상황이므로 다익스트라 유형임을 쉽게 파악할 수 있다. 점이 100개밖에 안되므로, 배열을 통해 충분히 관리할 수 있다. 추가적으로 모든 지점을 향해서 발사할 수 있으므로, 다익스트라에서 모든 정점에 대해서 확인해주면 된다. 다만, 처음 위치하는 곳에서는 무조건 걸어야하므로 따로 boolean flag를 통해 정리해주면 된다. Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long ll; typedef pair pii; typedef pair pdd; typedef pair pdi; int move_x[4] = {-1, 1, 0, 0}; int move..

Approach 정점에 cost가 있는 상황이므로, 위 문제와 거의 유사하다. https://viyoung.tistory.com/370 [백준 4485번] [Dijkstra] 녹색 옷 입은 애가 젤다지? Approach 전형적인 다익스트라 문제이다. DFS / BFS 문제처럼 상하좌우 방문해주면서 dist를 갱신해주면 된다. Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; typedef pair.. viyoung.tistory.com Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long ..

Approach 최단 시간으로 걸어야한다는 것에서 다익스트라를 떠올려주면 된다. 왔다갔다 하는 상황이므로 여러번 다익스트라를 돌려서 처리해주면 된다. 물론 플로이드 워샬로도 풀 수 있다. Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; typedef pair pii; typedef unsigned long long ull; typedef long long ll; typedef vector ullv1; typedef vector ullv2; const int INF = 2000000000; int main() { fastio; int n, m, x; cin >> n >> m >> x; x--; vector ed..

Approach 전형적인 다익스트라 문제이다. DFS / BFS 문제처럼 상하좌우 방문해주면서 dist를 갱신해주면 된다. Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; typedef pair pii; typedef unsigned long long ull; typedef long long ll; typedef vector ullv1; typedef vector ullv2; typedef tuple tiii; const int INF = INT_MAX; int move_x[4] = {-1, 1, 0, 0}; int move_y[4] = {0, 0, -1, 1}; int main() { fastio; int ..

Approach 아마 다익스트라 문제임은 쉽게 파악할 수 있을 것이다. 이 문제를 풀기위해 가장 중요한 점은, 각 경로 별로 통행료와 간선의 개수를 파악하는 것이다. 왜냐하면, 통행료가 올라감에 따라 간선의 개수가 많을수록 통행료가 증가하기 때문이다. 즉, 간선의 개수 별로 최소 통행료를 구하는 것이 필요하고 이를 DP느낌으로 처리해주면 된다. dist[i][j] : 출발점에서 정점 i까지 j만큼의 간선을 통과했을 때의 최소 통행료 Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; typedef pair pii; typedef unsigned long long ull; typedef tuple tiii; typ..

Approach 다익스트라의 구현을 잘 보면, 탐색 과정에서 의도적으로 최단 경로가 아닌 경우를 배제한다. 해당 경우들을 우선순위큐 자료구조로 정리하면, 쉽게 k번째 최단경로를 구할 수 있다. 추가적으로, 어떤 한 정점의 k번째 최단경로를 구하기 위해서 다른 정점의 k번째 최단경로 이후까지고 고려해야하는 것은 아닌지에 대한 의구심이 들 수 있다. 만약 특정 정점의 k + i 번째 최단경로를 활용해서 원하는 정점의 k번째 최단 경로를 구할 수 있다고 하자. 이때 최단 경로는 무조건 증가하므로 특정 정점의 k번쨰 최단 경로가 더 짧을 것이다. 따라서 k번째 정점만 모두 구해도 일반성을 잃지 않는다고 할 수 있다. Code #include #define fastio cin.tie(0)->sync_with_st..