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

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