Approach 다익스트라를 2번 돌리는 것은 쉽게 파악할 수 있다. 이 문제에서 가장 중요한 지점은, 최단 경로를 전부 찾고 해당하는 최단 경로를 지우는 것이다. 이를 위해 기존의 parent를 1개만 저장해둔 것에서 vector를 통해 저장해두면, 최단 경우에 해당하는 모든 간선들을 찾고 지울 수 있다. 추가적으로, 포인터 등을 활용해서 간선을 조금 더 효율적으로 지울 수는 있다. (toysmars님의 제출 코드 참고) 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 mov..

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