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))이다..

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 = 987654321; int main() { fastio; int n, m; cin >> n >> m; vector edge[n]; for(int i = 0; i > a >> b >> c; edge[a - 1].push_back({b - 1..

Approach 대표적인 다익스트라 문제이다. w가 양수인 최단 경로를 구하는 상황이므로 다익스트라로 구할 수 있다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair pii; const int INF = 987654321; int v, e; vector dist; vector edge; bool visited[20000]; int main(void) { fastio; memset(visited, 0, sizeof(visited)); cin >> v >> e; edge = vector(v); dist = vector(v); fill(dist.beg..

Approach 그래프 탐색 관련한 문제라는 것은 문제를 읽자마자 쉽게 파악할 수 있다. 문제 상황에서 가장 크리티컬한 지점은 탐색과정에서 보석을 얼마나 가지고 있는지를 기억해야한다는 것이다. 왜냐하면, 보석을 얼마나 가지고 있는지에 따라서 방문할 수 있는 지역이 달라지기 때문이다. 따라서 BFS를 돌리는 과정에서, 보석을 얼마나 가지고 있는지를 기억하고 있으면 된다. 같은 지역에 있는 보석은 1번만 주울 수 있으므로, 비트마스킹을 통해 1개의 정수로 어느 지역의 보석을 가지고 있는지를 쉽게 저장해놓을 수 있다. 추가적으로 같은 지역을 방문하더라도 보석이 달라지면 경향성이 달라지므로, visited를 2차원 배열로 잡는다. 위 문제와 비슷한 느낌으로 이해해주면 된다. https://viyoung.tist..

Approach 문제에서 이동 횟수의 최솟값을 묻는 상황이므로, BFS를 바로 떠올려주면 된다. 다만, 이 문제에서 되게 독특한 지점은 각 이동하는 상황에서 키를 가지고 있는지 여부가 굉장히 중요하다. 따라서 키를 가지고 있는지 여부를 set으로 넘겨줘도 되지만, 비트마스킹을 활용해주면 숫자 하나로 모든 것을 판단할 수 있게 된다. 추가적으로 visited도 신경써야 하는데, 키가 달라진다면 기존에 방문했던 곳이라도 양상이 달라질 수 있기 때문에 visited를 3차원으로 잡아주면 된다. 다음 문제와 비슷하게 느낌을 받았으면 충분하다. (위 문제도 단순히 같은 위치를 방문한다고 해서 같은 의미는 아니므로 차원을 1개 늘렸다.) https://viyoung.tistory.com/334 [백준 2206번] ..