eff3ct's st0rage Dev Blog

월반멘토링 3주차 set 풀이

04 Aug 2022

벌써 3주차..!!

Dijkstra / Floyd-Warshall / Bellman-Ford

1. 숨바꼭질 3 (Gold V)

tag : dijkstra, 0-1 bfs

각 위치를 노드로 생각하고 1초와 0초를 간선 가중치라고 생각할 수 있다. 그러면, 가중치가 있는 그래프 상에서 최단 거리를 찾는 문제로 변형된다. 이때, 가중치가 있는 그래프에서 최단 거리를 찾는 알고리즘으로, 다익스트라 알고리즘을 써서 찾아주면 된다.

즉, -1과 +1로 이동할 때는 가중치가 1이고 2 * X로 이동할 때는 가중치가 0인 그래프로 생각하면 된다. 가만 보면 가중치가 0과 1로 단 2개 밖에 없다. 이런 특수한 경우에는 다익스트라 알고리즘도 가능하지만, 특별한 BFS로도 풀 수 있다.

이것을 0-1 BFS라고 합니다. 저는 이 풀이에 대해서 다루지 않지만, 우연히 BFS로 푸신 분들이 의외로 많으셔서 왜 그게 되는지는 알아야 하니까.. 이런게 있다는 것을 알려드립니다. 0-1 BFS에 대한 자세한 설명은 나정휘님이 쓰신 이 글을 참고하세요!

코드 보기 
// https://www.acmicpc.net/problem/13549 //
#include <iostream>
#include <utility>
#include <queue>
#define INF 987654321

using namespace std;

bool isValid(int a) {
    if(0 <= a && a <= 1000000) return true;
    else return false;
}

int dijkstra(int N, int K) {
    if(N == K) return 0;
    int *cost;
    cost = new int[1000001];
    fill_n(cost, 1000001, INF);
    priority_queue<pair<int, int>> q; //{ cost, node }

    cost[N] = 0;
    q.push({ -cost[N], N });

    while(!q.empty()) {
        int nowPoint = q.top().second;
        int nowCost = -q.top().first;
        q.pop();

        if(cost[nowPoint] < nowCost) continue;

        int a = nowPoint - 1;
        int b = nowPoint + 1;
        int c = nowPoint * 2;

        if(isValid(a)) {
            int tmpCost = nowCost + 1;
            if(tmpCost < cost[a]) {
                cost[a] = tmpCost;
                q.push({ -tmpCost, a });
            }
        }
        if(isValid(b)) {
            int tmpCost = nowCost + 1;
            if(tmpCost < cost[b]) {
                cost[b] = tmpCost;
                q.push({ -tmpCost, b });
            }
        }
        if(isValid(c)) {
            int tmpCost = nowCost;
            if(tmpCost < cost[c]) {
                cost[c] = tmpCost;
                q.push({ -tmpCost, c });
            }
        }
    }
    int result = cost[K];
    delete[] cost;
    return result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K;
    cin >> N >> K;
    cout << dijkstra(N, K);
    return 0;
}

2. 키 순서 (Gold IV)

tag : dfs, floyd-warshall

두가지의 풀이가 있다. 하나는 DFS를 하는 방법이고, 하나는 플로이드-워샬 알고리즘을 사용하는 방법이다. 본인은 DFS 풀이가 더 쉽다고 생각하기에 DFS 풀이만 소개하도록 하겠습니다. 사실상 뜯어보면 같은 풀이고 시간복잡도도 \(\scriptsize O(N^{3})\) 동일하니 편한걸로 푸시면 됩니다.

먼저, \(\scriptsize a \rightarrow b :=\) “\(\scriptsize a\)가 \(\scriptsize b\)보다 키가 작다.” 이므로, 어떤 노드를 잡고 해당 노드를 시작점으로 DFS를 돌려 방문 가능한 노드들은 시작 노드보다 키가 큰 노드들이다. 반대로, 간선 방향이 반대로된 그래프가 있다고 해보자. 해당 그래프에서는 방향 간선이 반대의 의미를 갖는다. 즉, \(\scriptsize a \rightarrow b :=\) “\(\scriptsize a\)가 \(\scriptsize b\)보다 키가 크다.” 이므로, 이 그래프에서 DFS를 돌리면 키가 작은 노드들에 대한 정보를 얻을 수 있다.

어떤 특정 노드가 몇 번째로 키가 큰 건지 알려면 정방향 그래프, 역방향 그래프에서 방문 가능한 노드들을 모았을 때, 전부 모아져야 한다. 쉽게 말하자면, (자기보다 키가 큰 사람의 수 + 자기보다 키가 작은 사람의 수) = (자신을 제외한 모든 노드의 개수) 이니 모든 노드에 방문 가능해야하다. 그래야지 자신의 위치가 어딘지 확정된다.

문제 첫번째 예제에서 5번을 시작점으로 정방향 그래프 DFS를 수행하면, 2, 4, 6번에 방문 가능하다. 역방향 그래프 DFS를 수행하면, 1번에 방문 가능하다. 이때, 3번에는 방문이 불가능하므로 5번 노드는 몇번째인지 알지 못한다. 반면, 4번 노드는 모두 방문 가능하기 때문에 자신의 위치를 확정시킬 수 있다.

모든 노드들에 대해 이 방법을 그대로 적용시켜 DFS를 수행해주면 된다. 정방향 DFS / 역방향 DFS를 해주면 되고 적당히 잘 처리해주면 AC를 받을 수 있다.

플로이드-워샬 풀이도 비슷하다. 플로이드-워샬 알고리즘을 수행하면 all to all 최단 거리 정보를 얻을 수 있는데, 특정 노드로부터 다른 모든 노드들까지 거리 정보가 저장된다면 위치 확정이 된다는 의미이니 똑같이 풀 수 있다.

아래는 DFS풀이다.

코드 보기 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ppii = pair<int, pii>;

vector<int> forward_adj[505];
vector<int> backward_adj[505];
bool vst[505];

void dfs(int cur_node, bool is_back) {
    for(int& next_node : (is_back ? backward_adj : forward_adj)[cur_node]) {
        if(vst[next_node]) continue;
        vst[next_node] = true;
        dfs(next_node, is_back);
    }
}

int solve(int N) {
    bool check[505];

    int ret = 0;
    for(int v = 1; v <= N; ++v) {
        fill(check, check + 505, false);

        fill(vst, vst + 505, false);
        vst[v] = true;
        dfs(v, false);

        for(int i = 1; i <= N; ++i) {
            if(vst[i]) check[i] = true;
        }

        fill(vst, vst + 505, false);
        vst[v] = true;
        dfs(v, true);

        for(int i = 1; i <= N; ++i) {
            if(vst[i]) check[i] = true;
        }

        int cnt = 0;
        for(int i = 1; i <= N; ++i) {
            if(check[i]) cnt++;
        }

        if(cnt == N) ret++;
    }

    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M; cin >> N >> M;
    for(int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b;
        forward_adj[a].push_back(b);
        backward_adj[b].push_back(a);
    }

    cout << solve(N) << '\n';

    return 0;
}

3. 타임머신 (Gold IV)

tag : bellman-ford

누가봐도 벨만-포드 알고리즘 써달라는 문제다. 도시가 노드고 버스가 간선이다. 음수 사이클이 생기면, 무한히 시간을 되돌릴 수 있으니까 벨만-포드 알고리즘으로 음수 사이클 여부를 체크하고 최단 거리를 출력해주면 된다.

코드 보기 
// https://www.acmicpc.net/problem/1865 //
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#define INF 987654321

using namespace std;

vector<long long> dist(501, INF);

void solve(vector<pair<int, int>> (&adj)[501], int& N) {
    dist[1] = 0;
    for(int i = 0; i < (N - 1); ++i) {
        for(int j = 1; j <= N; ++j) {
            for(auto edge : adj[j]) {
                if(dist[j] != INF) {
                    dist[edge.first] = min(dist[j] + edge.second, dist[edge.first]);
                }
            }
        }
    }

    for(int i = 1; i <= N; ++i) {
        for(auto edge : adj[i]) {
            if(dist[i] != INF && dist[edge.first] > dist[i] + edge.second) {
                cout << "-1\n";
                return;
            }
        }
    }

    for(int i = 2; i <= N; ++i) {
        if(dist[i] != INF) {
            cout << dist[i] << '\n';
        }
        else cout << "-1\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    vector<pair<int, int>> adj[501];
    int N, M; cin >> N >> M;

    for(int i = 0; i < M; ++i) {
        int s, e, t; cin >> s >> e >> t;
        adj[s].push_back({e, t});
    }

    solve(adj, N);

    return 0;
}

4. 저울 (Gold III)

tag : dfs, floyd-warshall

2번 문제랑 사실상 동일한 문제다. 이번에는 묻는게 반전이 되었다. 비교 결과를 알 수 없는 물건 수를 출력하면 된다. 2번 풀이에서 살짝만 바꾸면 AC를 받을 수 있다. 따라서, 풀이는 생략함.

코드 보기 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ppii = pair<int, pii>;

vector<int> forward_adj[101];
vector<int> backward_adj[101];
bool vst[101];

void dfs(int cur_node, bool is_back) {
    for(int& next_node : (is_back ? backward_adj : forward_adj)[cur_node]) {
        if(vst[next_node]) continue;
        vst[next_node] = true;
        dfs(next_node, is_back);
    }
}

void solve(int N) {
    bool check[101];

    for(int v = 1; v <= N; ++v) {
        fill(check, check + 101, false);

        fill(vst, vst + 101, false);
        vst[v] = true;
        dfs(v, false);

        for(int i = 1; i <= N; ++i) {
            if(vst[i]) check[i] = true;
        }

        fill(vst, vst + 101, false);
        vst[v] = true;
        dfs(v, true);

        for(int i = 1; i <= N; ++i) {
            if(vst[i]) check[i] = true;
        }

        int cnt = 0;
        for(int i = 1; i <= N; ++i) {
            if(check[i]) cnt++;
        }

        cout << N - cnt << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M; cin >> N >> M;
    for(int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b;
        forward_adj[a].push_back(b);
        backward_adj[b].push_back(a);
    }

    solve(N);

    return 0;
}

5. 웜홀 (Gold III)

tag : bellman-ford

누가봐도 벨만-포드 알고리즘 좀 써달라고 소리치는 문제다. 타임머신이랑 풀이가 그냥 다르지 않다. 음수 사이클 여부만 체크해주면 된다. 풀이 생략.

코드 보기 
// https://www.acmicpc.net/problem/1865 //
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#define INF 987654321

using namespace std;

vector<int> dist(501, INF);

void solve(vector<pair<int, int>> (&adj)[501], int& N) {
    dist[1] = 0;
    for(int i = 1; i <= (N - 1); ++i) {
        for(int j = 1; j <= N; ++j) {
            for(auto edge : adj[j]) {
                dist[edge.first] = min(dist[j] + edge.second, dist[edge.first]);
            }
        }
    }

    for(int i = 1; i <= N; ++i) {
        for(auto edge : adj[i]) {
            if(dist[edge.first] > dist[i] + edge.second) {
                cout << "YES\n";
                return;
            }
        }
    }

    cout << "NO\n";
}

int main() {
    int TC; cin >> TC;
    while(TC--) {
        vector<pair<int, int>> adj[501];
        int N, M, W; cin >> N >> M >> W;

        fill(dist.begin(), dist.end(), INF);

        for(int i = 0; i < M; ++i) {
            int s, e, t; cin >> s >> e >> t;
            adj[s].push_back({e, t});
            adj[e].push_back({s, t});
        }

        for(int i = 0; i < W; ++i) {
            int s, e, t; cin >> s >> e >> t;
            adj[s].push_back({e, -t});
        }

        solve(adj, N);
    }

    return 0;
}

6. 미확인 도착지 (Gold II)

tag : dijkstra

은근히 문제가 복잡하기 때문에 잘 읽어줘야 한다. 요약하면, \(\scriptsize g-h\) 교차로를 지나면서 최단거리로 도달할 수 있는 후보노드들을 출력해주면 된다. 가질 수 있는 경로를 대략 표현해보면 아래와 같다.

\[s \rightarrow g \rightarrow h \rightarrow t\] \[s \rightarrow h \rightarrow g \rightarrow t\]

어느 정점을 먼저 방문하느냐에 따라 이렇게 두가지 케이스만 존재한다.

그럼, 알아야하는 정보는 \(\scriptsize s \rightarrow g\) 최단경로, \(\scriptsize h \rightarrow t\) 최단 경로, \(\scriptsize s \rightarrow h\) 최단경로, \(\scriptsize g \rightarrow t\) 최단 경로다.

이는 \(\scriptsize s, g, h\)를 시작으로 하는 다익스트라를 각각 돌려 얻어낼 수 있다. 후보 \(\scriptsize t\)에 대해 계속 경로를 만들어보며 해당 경로의 길이가 \(\scriptsize s\)로부터 \(\scriptsize t\)까지의 거리와 같은지 확인하는 걸로 가능한 후보임을 알 수 있다.

가능한 후보들은 골라내고 정리해서 오름차순으로 출력해주면 AC를 받을 수 있다.

코드 보기 
#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;
const int INF = 987654321;

void get_dist(vector<vector<pii>>& adj, int s, vector<int>& dist) {
    priority_queue<pii, vector<pii>, greater<pii>> pq; //dist, node
    dist[s] = 0;
    pq.push({0, s});

    while(!pq.empty()) {
        int now_dist = pq.top().first;
        int now_node = pq.top().second;
        pq.pop();

        if(now_dist > dist[now_node]) continue;

        for(auto& next : adj[now_node]) {
            int next_node = next.first;
            int next_dist = next.second + now_dist;

            if(next_dist < dist[next_node]) {
                dist[next_node] = next_dist;
                pq.push({next_dist, next_node});
            }
        }
    }
}

void solve(vector<vector<pii>>& adj, int s, int g, int h, vector<int>& canditate) {
    int n = int(adj.size());
    vector<int> dist_s(n, INF);
    vector<int> dist_g(n, INF);
    vector<int> dist_h(n, INF);

    get_dist(adj, s, dist_s);
    get_dist(adj, g, dist_g);
    get_dist(adj, h, dist_h);

    vector<int> ans;

    int x;
    for(int i = 0; i < int(adj[g].size()); ++i) {
        if(adj[g][i].first == h) {
            x = i;
            break;
        }
    }
    int dist_gh = adj[g][x].second;

    //s->g->h->t
    int min_dist_sght = dist_s[g] + dist_gh;
    for(auto& c : canditate) {
        if(min_dist_sght + dist_h[c] == dist_s[c]) ans.push_back(c);
    }

    //s->h->g->t
    int min_dist_shgt = dist_s[h] + dist_gh;
    for(auto& c : canditate) {
        if(min_dist_shgt + dist_g[c] == dist_s[c]) ans.push_back(c);
    }

    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());

    for(auto& e : ans) cout << e << ' ';
    cout << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int T; cin >> T;

    while(T --> 0) {
        int n, m, t; cin >> n >> m >> t;
        int s, g, h; cin >> s >> g >> h;
        vector<vector<pii>> adj(n + 1);
        for(int i = 0; i < m; ++i) {
            int a, b, d; cin >> a >> b >> d;
            adj[a].push_back({b, d});
            adj[b].push_back({a, d});
        }

        vector<int> canditate(t);
        for(int& e : canditate) cin >> e;

        solve(adj, s, g, h, canditate);
    }

    return 0;
}

7. 합리적인 이동경로 (Gold I)

tag : dfs, dijkstra, tree-dp, topology-sort(?)

\(\scriptsize T\)와 가까워진다는 조건이 무엇을 의미할까? 간선을 타고 이동했을 때, \(\scriptsize T\)까지 최단거리값이 짧아진다는 의미이다. 그럼 슨생님.. 모든 노드로부터 \(\scriptsize T\)까지 거리가 필요한 거 아닌가요? 물론 그렇게 생각할 수도 있다. 그러나, 반대로 생각해서 \(\scriptsize T\)부터 모든 노드의 거리를 아는 방법이 더 쉽고 더 빠르다. 그러니 우리는 그렇게 생각하도록 합시다.

\(\scriptsize T\)부터 모든 노드까지의 거리는 다익스트라 알고리즘 한번이면 구할 수 있다. 이제, 그럼 \(\scriptsize T\)와 가까워지며 이동할 수 있게는 되었다. 어떤 노드 \(\scriptsize u\)에서 다른 노드 \(\scriptsize v\)로 이동할 때, 현재 \(\scriptsize dist(u) > dist(v)\)인지 확인하고 이동하면 되기 때문이다.

\(\scriptsize T\)랑 가까워지는곳으로 이동하는 이 조건만으로도 그래프가 트리로 고정이 되는 것 같은데, 본인은 왜 그런지 잘 이해가 안됐기에.. 일단 해당 조건을 만족하도록 그래프를 새로 만드는 과정을 거쳤다. 그런 이후 위상 정렬 + DAG dp로 문제를 해결했다.

\(dp(cur) :=\) “\(cur\)까지 이동 경로의 개수”

라고 정의하면, 이런 관계식을 얻을 수 있다.

\[dp(cur) = \sum_{prev \in adj_{prev}(cur)}dp(prev)\]

이제, 위상정렬을 수행하면서 dp를 해주면 되니까 답을 구할 수 있다. dp를 하고나면, 2번 노드에 저장된 카운트 값을 출력해주면 된다.

.

.

.

.

.

.

인데.. 위상정렬 필요없이 최단거리 정보를 활용한 트리 dp로 풀리는 모양이다. 난 트리로 안 생겼을 수 있다고 생각해서 위상정렬을 넣었는데 왜 그런지 아시는 분은 댓글좀 남겨주세요. 하여튼, 이런식으로 풀면 플래5 정도 난이도를 가진 문제라고 생각한다. 쉽진 않은 문제이니 천천히 풀어보시길 바랍니다.

코드 보기 
 #include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ppii = pair<int, pii>;

vector<pii> adj[1010];
vector<int> tree_adj[1010];
int in_degree[1010];
ll dist[1010];
const ll INF = 1e18;

void dijkstra() {
    fill(dist, dist + 1010, INF);

    priority_queue<pii, vector<pii>, greater<pii>> pq;

    dist[2] = 0;
    pq.push({0, 2});

    while(!pq.empty()) {
        int cur_node = pq.top().second;
        ll cur_dist = pq.top().first;
        pq.pop();

        if(cur_dist > dist[cur_node]) continue;

        for(pii& next : adj[cur_node]) {
            int next_node = next.first;
            ll next_dist = next.second + cur_dist;

            if(next_dist < dist[next_node]) {
                dist[next_node] = next_dist;
                pq.push({next_dist, next_node});
            }
        }
    }
}

void construct_tree() {
    bool visit[1010];
    fill(visit, visit + 1010, false);

    function<void(int)> dfs = [&](int cur) {
        for(pii& nxt : adj[cur]) {
            int next = nxt.first;

            if(dist[cur] > dist[next]) {
                tree_adj[cur].push_back(next);
                in_degree[next]++;

                if(visit[next]) continue;
                
                visit[next] = true;
                dfs(next);
            }
        }
    };

    visit[1] = true;
    dfs(1);
}

int get_path_count() {
    ll count[1010];
    fill(count, count + 1010, 0);

    queue<int> q;
    q.push(1);
    count[1] = 1;

    while(!q.empty()) {
        int cur_node = q.front();
        q.pop();

        for(int& next_node : tree_adj[cur_node]) {
            count[next_node] += count[cur_node];
            if(--in_degree[next_node] == 0) 
                q.push(next_node);
        }
    }

    return count[2];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M; cin >> N >> M;
    for(int i = 0; i < M; ++i) {
        int A, B, C; cin >> A >> B >> C;
        adj[A].push_back({B, C});
        adj[B].push_back({A, C});
    }

    dijkstra();
    construct_tree();
    cout << get_path_count() << '\n';

    return 0;
}

8. 전투 시뮬레이션 (Platinum V)

tag : dijkstra, simulation, implementation

누가봐도 귀찮은 구현 시뮬레이션 문제다. 풀 마음이 아직 안생겨서.. 풀고나서.. 풀이 올리도록 하겠습니다 ㅎㅎ

edit : 2022/08/04 22시 문제 풀어왔습니다

다익스트라를 잘 활용해서 풀 수 있는 좀 많이많이 빡센 구현 문제다. 본인은 다 풀어놓고, \(\scriptsize 500 \cdot 500 = 25000\) 으로 잘못생각해서 한 4시간 날렸는데, \(\scriptsize 500 \cdot 500 / 4 = 62500\) 이니 알아두길 바랍니다.. (나만 산수 못해) 여튼 배열 크기 잘못 잡았더니 WA받고(RE를 띄워줘야 하는데 안떴음) n시간 날려서 억울함.

기본적으로, \(\scriptsize H \times W\) 사이즈의 맵에서 유닛들을 조건에 맞게 옮겨주는 문제다. 조건이 좀 많아서 구현이 어지러울 뿐이다. 중요한 조건을 정리하자면, 다음과 같다.

  1. 각 유닛은 자신의 이동력보다 작거나 같은 거리만큼 움직일 수 있다.

  2. 다른 세력의 유닛이 인접하면 교전이 시작되니 피해서 움직여야 한다.

  3. 다만, 2번의 경우 도착하는 위치가 교전이 시작될 위치면 예외로 치자.

  4. 교전을 하고 있는 상태에서 약진을 통해 해당 위치를 벗어날 수 있다.

  5. 이동할 곳이 유닛이 있거나 -1의 험준도를 가지는 위치면 불가능하다.

이걸 잘 구현해주면 된다. 말만 쉽지 오래걸린다. 먼저, 1번 조건은 다익스트라 알고리즘으로 해결할 수 있다. 각 노드별로 가중치가 설정되어 있는데, 이를 이용해 다익스트라를 돌려 작은 가중치를 따라가는 경로로 이동하는게 항상 이득이다. 헉, 그런데 이렇게 \(\scriptsize T\)번 다익스트라를 돌리면 \(\scriptsize O(T \cdot HWlog(HW))\)아닌가요? 유의미한 지적이다. 그런데, 문제 조건에 지형의 험준도는 0이 될 수 없고 항상 1 ~ 3까지의 값을 가진다고 하네요. 이때, 각 유닛별 최대 이동력은 20이기 때문에 상하좌우 20칸 내부 범위에서만 다익스트라 알고리즘이 수행됨을 알 수 있다!

그렇기 때문에, 매번 다익스트라를 돌린다고 하더라도 충분히 시간내에 코드가 돌아갈 것임을 짐작할 수 있다. 2번의 구현은 사람마다 다를 수 있다. 나는 각 세력별로 유닛이 놓인 위치와 해당 위치의 상하좌우에 따로 표시를 해서 표시된 구간에 들어서지 못하도록 구현했다. 좌표 이동을 하면, 원래 위치에 표시된 값들은 다시 지워주고, 이동한 위치에 새로 표시해주면 된다. 아래 코드에서 party_0, party_1이 그 역할을 하는 배열이다.

3번은 적당히 다익스트라를 수행하면서 예외로 처리해주자. 내가 구현한 방식대로 구현하게 된다면 4번은 신경쓰지 않아도 된다. 다익스트라에 쓰이는 시간을 아끼기 위해서, 최단거리 탐색에 앞서서 갈려는 좌표가 -1이거나 유닛이 이미 존재하는지 먼저 체크하자. 이게 5번의 처리 방법이었다.

요렇게만 구현하면 풀릴 줄 알았지만!!! 세상은 차가운 곳이었다..

조금 최적화를 해줘야 시간 내에 통과된다. 구현에 따라 최적화가 필요없을 수 있지만, 다익스트라를 돌릴 때 이동할 좌표가 힙에서 나오면, 바로 함수를 종료해주도록 하자. 이 정도의 최적화를 해주면 시간 내에 풀이가 통과된다.

다익스트라 부분만 따로 보자.

// 다익스트라 구현 파트

// 초기 좌표 거리값 0으로 설정
dist[y][x] = 0;
pq.push({0, y, x});
while(!pq.empty()) {
    // 현재 좌표 받아오기
    int cur_y = pq.top().y;
    int cur_x = pq.top().x;
    int cur_dist = pq.top().dist;
    pq.pop();

    // 만약, 이미 이동할 좌표에 도달했으면 함수 종료
    if(cur_y == a && cur_x == b) return true;
    
    if(cur_dist > dist[cur_y][cur_x]) continue;

    for(int i = 0; i < 4; ++i) {
        // 다음 좌표 받아오기
        int next_y = cur_y + dy[i];
        int next_x = cur_x + dx[i];

        // 다음 좌표가 내부인지 검사
        if(next_x < 0 || next_x >= W || next_y < 0 || next_y >= H) continue;
        // 해당 좌표 험준도 값이 -1이 아니어야 함.
        if(r[ m[next_y][next_x] ] == -1) continue;
        // 해당 좌표에 다른 세력이 영향을 미칠 수 있는 지 체크해줘야 함. (인접한 곳인지 체크)
        if(party[next_y][next_x] && !(next_y == a && next_x == b)) continue;

        int next_dist = cur_dist + r[ m[next_y][next_x] ];

        // 현재 거리값이 더 작고, 이동력보다 거리를 덜 이동했을 때 힙에 삽입
        if(next_dist < dist[next_y][next_x] && next_dist <= u[unit_n].m) {
            dist[next_y][next_x] = next_dist;
            pq.push({next_dist, next_y, next_x});
        }
    }
}

구현을 보면 알겠지만, 문제에서 시키는 조건을 잘 넣어주면 성공적으로 다익스트라를 수행할 수 있다. 자세한 구현은 아래 코드를 참고하자

코드 보기 
// 아직 없어.. 우히히

// edit : 2022 / 08 / 04
// 이제 있어! 헤헤
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ppii = pair<int, pii>;

struct unit {
    int m, party, y, x;
};

int N, H, W; // N : the number of terrain types, H : row, W : column
int m[501][501]; // map
int r[10]; // terrain values
unit u[70707];
int party_0[501][501], party_1[501][501];
int unit_place[501][501];
int dist[501][501];

int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};
const int INF = 1e9;

void mark_party(int t, int a, int b, bool plus) {
    int delta = plus ? 1 : -1;
    auto& party = (t == 0) ? party_0 : party_1;
    party[a][b] += delta;
    unit_place[a][b] += delta;
    for(int i = 0; i < 4; ++i) {
        int ny = a + dy[i];
        int nx = b + dx[i];

        if(nx < 0 || nx >= W || ny < 0 || ny >= H) continue;

        party[ny][nx] += delta;
    }
}

bool dijkstra(int unit_n, int a, int b) {
    int y = u[unit_n].y;
    int x = u[unit_n].x;
    auto& party = (u[unit_n].party == 0) ? party_1 : party_0;

    struct node {
        int dist, y, x;

        bool operator<(const node& x) const {
            return dist > x.dist;
        }
        bool operator>(const node& x) const {
            return dist < x.dist;
        }
    };
    priority_queue<node, vector<node>, greater<node>> pq;
    for(int i = 0; i < 501; ++i)
        fill(dist[i], dist[i] + 501, INF);

    dist[y][x] = 0;
    pq.push({0, y, x});
    while(!pq.empty()) {
        int cur_y = pq.top().y;
        int cur_x = pq.top().x;
        int cur_dist = pq.top().dist;
        pq.pop();

        if(cur_y == a && cur_x == b) return true;
        
        if(cur_dist > dist[cur_y][cur_x]) continue;

        for(int i = 0; i < 4; ++i) {
            int next_y = cur_y + dy[i];
            int next_x = cur_x + dx[i];

            if(next_x < 0 || next_x >= W || next_y < 0 || next_y >= H) continue;
            if(r[ m[next_y][next_x] ] == -1) continue;
            if(party[next_y][next_x] && !(next_y == a && next_x == b)) continue;

            int next_dist = cur_dist + r[ m[next_y][next_x] ];

            if(next_dist < dist[next_y][next_x] && next_dist <= u[unit_n].m) {
                dist[next_y][next_x] = next_dist;
                pq.push({next_dist, next_y, next_x});
            }
        }
    }

    return false;
}

void move_unit(int unit_n, int a, int b) {
    if(r[ m[a][b] ] == -1) return;
    if(unit_place[a][b]) return;
    if(dijkstra(unit_n, a, b)) {
        mark_party(u[unit_n].party, u[unit_n].y, u[unit_n].x, false);
        mark_party(u[unit_n].party, a, b, true);
        u[unit_n].y = a, u[unit_n].x = b;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N >> H >> W;

    for(int y = 0; y < H; ++y) {
        for(int x = 0; x < W; ++x) {
            cin >> m[y][x];
        }
    }

    for(int i = 1; i <= N; ++i)
        cin >> r[i];

    int M; cin >> M;
    for(int i = 1; i <= M; ++i) {
        int m, t, a, b; cin >> m >> t >> a >> b;
        u[i] = {m, t, a, b};
        mark_party(t, a, b, true);
    }

    int K; cin >> K;
    while(K --> 0) {
        int u, a, b; cin >> u >> a >> b;
        move_unit(u, a, b);
    }

    for(int i = 1; i <= M; ++i) 
        cout << u[i].y << ' ' << u[i].x << '\n';

    return 0;
}

9. K번째 최단경로 찾기 (Platinum IV)

tag : dijkstra, priority_queue

웰노운류의 문제다. 모르면 맞는..

노드 개수만큼의 힙(max)을 만들어주고, 기본적으로는 다익스트라를 수행할거에요.

각자 노드마다 자신의 힙이 있고, 힙에는 해당 노드까지의 거리정보가 쌓인다. 이제 힙 크기가 \(\scriptsize K\)개가 되도록 관리 해주면 된다. 힙 크기가 \(\scriptsize K\)보다 작으면 거리정보를 push해주고, 힙 크기가 \(\scriptsize K\)이면 top과 비교해서 작을 때, top을 pop하고 거리 정보를 push해주면 된다.

이렇게 관리하면, 다익스트라 알고리즘이 모두 수행되었을 떄, 각 노드별 힙의 top에는 \(\scriptsize K\)번째로 긴 최단경로의 길이가 저장된다. 이때, 힙의 크기가 \(\scriptsize K\)보다 작으면 그것은 \(\scriptsize K\)번째 최단 경로가 없다는 뜻이니 -1을 출력하면 된다.

자세한 것은 코드를 보며 이해하도록 하자.

코드 보기 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ppii = pair<int, pii>;

vector<vector<pii>> adj(1001);
priority_queue<int> max_heap[1001];

void solve(int k) {
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, 1});
    max_heap[1].push(0);

    while(!pq.empty()) {
        int now_node = pq.top().second;
        int now_dist = pq.top().first;
        pq.pop();

        for(pii& next : adj[now_node]) {
            int next_node = next.first;
            if((int)max_heap[next_node].size() < k) {
                max_heap[next_node].push(now_dist + next.second);
                pq.push({next.second + now_dist, next_node});
            }
            else if(max_heap[next_node].top() > now_dist + next.second) {
                max_heap[next_node].pop();
                max_heap[next_node].push(now_dist + next.second);
                pq.push({next.second + now_dist, next_node});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, m, k; cin >> n >> m >> k;
    for(int i = 0; i < m; ++i) {
        int a, b, c; cin >> a >> b >> c;
        adj[a].push_back({b, c});
    }

    solve(k);

    for(int i = 1; i <= n; ++i) {
        if((int)max_heap[i].size() < k) cout << "-1\n";
        else cout << max_heap[i].top() << '\n';
    }

    return 0;
}

10. 밤편지 (Platinum V같은 Gold I)

edit : 2022/08/05 hibye1217님이 너무 좋은 문제를 들고오셔서 set에 추가했습니다.

tag : floyd-warshall, offline-query

선린은 낭만 있는 고등학교네요.. 아무튼 진짜 야무진 플로이드-워샬 알고리즘을 쓰는 문제다. 플로이드-워샬 알고리즘은 근본적으로 DP이다. 이 DP에 대해 정확한 이해를 하고 있으면 풀 수 있는 문제다.

먼저, 반딧불이 상수 \(\scriptsize C\)를 가지고 있고 \(\scriptsize 2^{C}\) 방울 이상 마시면 날아가지 못한다고 한다. 이는 경로상에 출발지와 도착지를 제외하고는 노드 번호가 \(\scriptsize C\)이상이 되면 안된다는 의미이다. 수학으로 설명하는게 깔끔하지만, 직관적인 이해가 문제 푸는데는 더 도움이 되기 때문에 왜 그렇게 해야하는지 러프하게 설명해보겠다.

경로상의 이슬을 모은 값은 \(\scriptsize \sum_{x} 2^{x}\) 이다. 이 값이 \(\scriptsize 2^{C}\) 보다 작아야 이동이 가능하다. 이진수 표현법으로 한 번 표현해보자.

\[2^{C} = 100000 ... 000\] \[\sum_{x}2^{x} = 010110 ... 101\]

(정확한 값은 아니고 예시를 들면 이렇다는 것)

\(\scriptsize 2^{C}\)를 넘기지 않으려면, \(\scriptsize C\)번째 자리 미만에서만 비트가 켜져 있으면 된다. 켜진 비트 하나하나가 \(\scriptsize 2^{x}\)와 같기 때문에 그렇다. 즉, \(\scriptsize C\)번 보다 작은 노드들로 경로가 구성되어 있어야 조건을 만족할 수 있다.

조건 하나를 드디어 해석했다. 쿼리 \(\scriptsize (C, s, e)\)는 \(\scriptsize C\)번 미만으로 구성된 경로에서 최단 경로를 찾으면 된다!

그런데, 문제는 \(\scriptsize C\)가 여러개가 주어지고 \(\scriptsize (s, e)\) 조합이 매우 많다는 점이다. 그럼, all to all 최단 경로 알고리즘이 필요하고, 각 \(\scriptsize C\)마다 뭔가 달라져야 할 것 같다.

우리가 아는 all to all 최단 경로 알고리즘은 플로이드-워샬 알고리즘이다. 이걸 활용하면 문제를 풀 수 있다. 해답은 플로이드-워샬의 dp 정의식에 있었다. dp 정의식을 공부해보자.

\(\small dp(i, j, k) := "i\) 에서 \(\small j\)까지 \(\small [1, 2, ..., k]\) 꼭짓점을 경유지로 삼을 때, 최단거리”

라고 정의하자. 어떤 최단거리는 \(\scriptsize k\)를 경유지로 삼는 최단거리와 그렇지 않은 최단거리 중 하나에 무조건 속한다. 따라서, 다음과 같은 dp 관계식을 유도할 수 있다.

\[\small dp(i, j, k) = \min(dp(i, j, k - 1), dp(i, k, k - 1) + dp(k, j, k - 1))\]

보통 별 생각 없이 쓰는 세제곱 짜리 반복문에 이런 내용이 담겨있다. dp 정의식을 잘 생각해보면, 요걸 이용해서 \(\scriptsize C\)번 노드 미만으로 구성된 최단 경로 값을 구해낼 수 있다.

여기서, 풀이가 둘로 나뉜다.

  1. dp 식 그대로 해결하기
  2. 오프라인 쿼리로 해결하기

본인은 2번으로 해결했으니, 2번으로 설명해보겠습니다. (메모리 덜 먹고 좀 더 빠른듯)

먼저, 오프라인 쿼리란 질의가 들어온 것을 그때그때 처리하지 않고, 질의들을 모아뒀다가 나중에 처리하는 기법을 의미한다. 반대로 온라인 쿼리는 질의가 들어올 때마다 처리해주는 기법이다.

쿼리들을 모조리 다 받아주자. 그런 뒤 쿼리들을 \(\scriptsize C\)에 대해 오름차순으로 정렬해주고, 이제 쿼리를 하나식 꺼내서 dp식의 \(\scriptsize k\)값을 \(\scriptsize C\)미만 까지 업데이트 시켜주면 된다. 그런 뒤 처리한 결과를 이용해 따로 정답 배열에 집어 넣자. 이걸 모든 쿼리에 해주면 답을 구할 수 있다.

아마 코드를 보고 분석하는 편이 더 이해가 빠를 것이다.

꽤나 어려운 문제이니 찬찬히 한 번 풀어보세요~

코드 보기 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ppii = pair<int, pii>;

ll ans[505050];
ll dist[303][303];
int N, Q; 

const ll INF = 1e18;

struct query {
    int C, s, e, idx;
};

void update_dist(int k, int c) {
    for(int t = k; t < min(c, N + 1); ++t) {
        for(int i = 1; i <= N; ++i) {
            for(int j = 1; j <= N; ++j) {
                dist[i][j] = min(dist[i][j], dist[i][t] + dist[t][j]);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N >> Q;
    for(int i = 1; i <= N; ++i) {
        for(int j = 1; j <= N; ++j) {
            cin >> dist[i][j];
            if(dist[i][j] == 0) dist[i][j] = INF;
        }
    }
    for(int i = 1; i <= N; ++i) dist[i][i] = 0;

    vector<query> qrys;
    for(int i = 0; i < Q; ++i) {
        int C, s, e; cin >> C >> s >> e;
        qrys.push_back({C, s, e, i});
    }

    sort(qrys.begin(), qrys.end(), [&](const query& a, const query& b) {
        return a.C < b.C;
    });

    int k = 1;
    for(auto& q : qrys) {
        int cur_C = q.C;
        update_dist(k, cur_C);
        k = cur_C;
        ans[q.idx] = (dist[q.s][q.e] == INF ? -1 : dist[q.s][q.e]);
    }

    for(int i = 0; i < Q; ++i)
        cout << ans[i] << '\n';

    return 0;
}

Related posts