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..

Approach 위 문제와 거의 유사. https://viyoung.tistory.com/365?category=884242 [백준 1162번] [Dijkstra] 도로포장 Approach 위 문제와 유사하다. https://viyoung.tistory.com/335 [백준 14442번] [BFS] 벽 부수고 이동하기 2 Approach https://viyoung.tistory.com/334 [백준 2206번] [BFS] 벽 부수고 이동하기 Approach 표면.. viyoung.tistory.com 위 문제에서 k가 1인 경우를 구하는 것과 완벽하게 동일하다. 백준 1162번과 달리, 차원을 올라갈 수 있는 경우가 항공편이 존재하였을 때이므로 그 부분만 신경써주면 완벽하게 동일한 문제이다. Code ..

Approach 위 문제와 유사하다. https://viyoung.tistory.com/335 [백준 14442번] [BFS] 벽 부수고 이동하기 2 Approach https://viyoung.tistory.com/334 [백준 2206번] [BFS] 벽 부수고 이동하기 Approach 표면적으로 보면 BFS 대표 유형과 유사해보인다. 다만, 일반적인 문제와 달리 1칸 벽을 뚫을 수 있다는 측면을 추가.. viyoung.tistory.com 위 문제와 상황자체는 완벽히 유사하나, 그래프에서 가중치가 존재하기 때문에 BFS가 아닌 다익스트라로 해결해주면 되는 것이다. Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace s..

Approach 최단 경로의 길이를 물어보는 것에서 다익스트라 문제임을 쉽게 파악할 수 있다. 이 문제에서 눈여겨 봐야할 지점은 반드시 거쳐야하는 정점이 있다는 것이다. 잠시 기억을 더듬어서 고등학교 경우의 수 문제에서 최단거리를 구할 때, 특정한 지점을 반드시 지나는 문제를 어떻게 풀었는지를 잘 생각해보자. 아마도 특정한 지점을 기준으로 분할해서 풀었던 기억이 있을 것이다. 마찬가지로 위 문제도 특정한 지점을 기준으로 분할해서 풀어주면 된다. 두 정점을 순서대로 v1, v2라고 하고, d(a, b)를 a부터 b까지 가는데 필요한 최단 경로의 길이라고 정의하자 d(1, N) = min(d(1, v1) + d(v1, v2) + d(v2, N), d(1, v2) + d(v2, v1) + d(v1, N))이다..