Approach 문제를 잘 관찰해보면, 위에서 표현한 2차원 각 공간에 있을 수 있는 물의 높이는 다음과 같은 절차를 거쳐서 결정하게 된다. 1. 외부와 직접적으로 마주하고 있는 공간은 구멍의 높이에 맞춰서 무조건 높이가 형성이 된다. 2. 외부와 직접적으로 마주하고 있는 공간과 직접적으로 구멍이 뚫려있는 경우, 뚫린 구멍의 높이와 외부와 직접적으로 마주하고 있는 공간의 높이값 중 최댓값으로 결정된다. (잘 생각해보면 자명하다.) 3. 2의 과정을 반복함으로써 해당 영역에 위치한 물의 높이를 구할 수 있게 된다. 이때, 물이 계속해서 빠져나가는 상황이므로 넘치게 하는 최소 경계값을 구하는 것과 같고, 이는 다익스트라 문제로 회귀할 수 있게 된다. 최소값을 구해나간다는 점에서 dist를 업데이트하고 pq에..

Approach 문제를 잘 관찰해보면, 현재 방문했던 주유소 중 주유 비용이 가장 싼 것이 무엇인지를 저장해두는 것이 중요하다는 것을 쉽게 파악할 수 있다. 추가적으로, 현재까지의 주유 비용이 가장 싼 것이 어느 것인지에 따라서 특정 점까지 방문하는데 필요한 비용이 다르므로 DP처럼 차원을 1개 더 잡아줘서 다익스트라를 돌려주면 된다. https://viyoung.tistory.com/380 [백준 10217번] [Dijkstra / DP] KCM Travel Approach 잘 생각해보면, 비용 단위로 최단거리를 구해주면 된다. https://viyoung.tistory.com/369 문제와 유사하다. Code #include #define fastio cin.tie(0)->sync_with_stdio..

Approach 정해진 출발점을 기준으로 최단거리가 m보다 작으면 방문할 수 있는 정점이라는 아이디어를 파악했으면 모든 정점을 출발점으로 설정하고, 다익스트라를 통해 최단거리가 m보다 더 작은 모든 정점에 속한 아이템의 수를 다 더해준 뒤 그 중 최댓값을 출력해주면 된다. 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}; const int INF = 1000000000; //ElogV * V int main() { fastio; i..

Approach 다익스트라를 돌리되, parent 배열을 따로 잡아줘서 역추적해주면 된다. 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}; const int INF = 200000000; int main() { fastio; int n, m; cin >> n >> m; vector edge[n]; for(int i = 0; i > a >> b >> c; edge[a - 1].pu..

Approach 잘 생각해보면, 비용 단위로 최단거리를 구해주면 된다. https://viyoung.tistory.com/369 문제와 유사하다. Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long ll; typedef pair pii; typedef tuple tiii; int move_x[4] = {-1, 1, 0, 0}; int move_y[4] = {0, 0, -1, 1}; const int INF = 100000000; int main() { fastio; int t; cin >> t; while(t--){ int n, m, k; cin >> n >> m >> k; vec..

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