BOJ 18253 최단경로와 쿼리 & SWEA 7509 최소 비용 경로 쿼리

문제 링크

백준 18253 최단경로와 쿼리
SWEA 7509 최소 비용 경로 쿼리 (로그인 필요)

문제 설명

두 문제는 가로-세로 조건이 반대인 점을 제외하고는 거의 같은 문제이다.
여기서는 백준의 문제를 기준으로 풀어보려고 한다.

N x M 의 정수 배열이 주어지고, 두 좌표 사이에서 가중치 합이 가장 적은 최소경로 비용을 구하는 문제이다.

• N은 1~5
• M은 1~100,000
• 총 요청 쿼리 수(Q)는 1~100,000이다.

여기서 주목할 점은 두 가지다.

1. N이 5로 매우 작다는 점 : M에 대한 접근 횟수만 최적화하면 된다.
2. 쿼리 수(Q)가 상당히 많다 : 쿼리마다 매번 계산을 수행한다면 매우 비효율적일 것이다.

따라서 이분 탐색 + 다익스트라 알고리즘을 활용하여 문제를 해결할 수 있다.
우선 아래와 같은 배열(array)을 생각해보자.

쿼리의 시작,끝 지점이 위와 같이 서로 반대편에 위치한다면, 그 경로는 반드시 가운데 열(mid)를 지날 것이다.

이때 mid의 첫 번째 행(array[mid][1])을 지나는 최단거리는

([mid][1] → Q1까지의 거리) + ([mid][1] → Q2까지의 거리) - array[mid][1]의 가중치

와 같다.
이러한 계산을 N번 수행하면, mid를 지나는 모든 최단경로를 구할 수 있다.

한편, 아래처럼 mid를 지나지 않는 경로도 존재한다.

따라서 mid를 기준으로 좌,우 측에도 동일한 계산을 수행해야 한다. 이때 이분탐색에서의 접근방식을 활용해보자.

mid의 좌측에서는 Q1,Q2가 모두 좌측에 있는 쿼리들에 대해서만 계산을 수행하면 된다. (Q1,Q2가 양쪽에 걸쳐 있을 경우에는 항상 mid를 지나쳤을 것이므로 이미 최단경로를 찾았다는 것이 보장된다.) 따라서 이분탐색을 수행할 시에 필요한 query들에 대해서만 계산함으로써 시간을 단축할 수 있다.

시간복잡도

• 이분탐색 : O( logM )
• 다익스트라를 각각 N번씩 수행 : O( N )
• 다익스트라 : O( MN log(MN) )
  • 우선순위 큐를 이용한 알고리즘에서 O( E logE ) 이므로
  • E = 4 M N
  • O( E logE ) = O( MN log(MN) )
• 총 O( MN^2 log(MN) log(M) )
• M >> N 인 점을 감안하면
• O( M (log(M))^2 ) 이다.

시간초과 해결

위 방법으로 코드를 작성했음에도 시간초과가 발생했다. 이런저런 방법을 써본 끝에,, 아래 세 방법을 모두 사용해서야 해결되었다.

시간초과 해결 1 : endl 대신 “\n”

endl 과 "\n" 은 출력결과는 동일하지만, 내부 동작은 다르다.

endl 에서는 출력을 위한 임시 메모리 공간인 출력 버퍼를 비우는 작업을 수행하기 때문에 자주 실행하면 비효율적이다.

endl 대신 "\n" 을 사용함으로써 1% → 8% 까지 진행시킬 수 있었다.

https://yechoi.tistory.com/48

시간초과 해결 2 : priority_queue 에서 vector 대신 struct

기존 priority_queue에서는 vector를 사용했다. vector의 경우 여유 메모리를 미리 할당하기 때문에 최적화가 어렵고, 부가적인 작업이 수행된다. 이러한 점이 문제가 되었던 것 같다.

이를 구조체로 변경하니 진행도가 증가했다. (8% → 2X%)

시간초과 해결 3 : 배열 초기화

이분탐색 후 다익스트라를 수행하는 과정에서 fill 함수를 사용했었다.
fill의 경우 이분탐색으로 필요한 배열의 크기가 매우 작을 때에도 배열 전체를 초기화했기 때문에 시간초과가 발생한 것으로 보인다.

이런저런 시도 끝에 결국 통과되었다..!!

백준 코드 (C++)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

typedef long long ll;

struct Query {
    pair<int,int> from, to;
    ll ans;

    void constructor(int r1, int c1, int r2, int c2) {
        if (c1 > c2) {
            swap(r1, r2);
            swap(c1, c2);
        }
        from = {r1, c1};
        to = {r2, c2};
        ans = 1e18;
    }
};

struct Node {
    ll cost;
    int row, col;
    bool operator < (const Node &t) const {
        return cost > t.cost;
    }
};

Query queries[100001];

int N, M, Q;
int mmap[6][100001];
ll dist[6][100001];
int dr[] = {1, -1, 0, 0};
int dc[] = {0, 0, 1, -1};

void dijkstra(int r0, int c0, int left, int right){
    for (int r = 1; r <= N; ++r) {
        for (int c = left; c <= right; ++c) {
            dist[r][c] = 1e18;
        }
    }

    priority_queue<Node> pq;
    pq.push({mmap[r0][c0], r0, c0});
    dist[r0][c0] = mmap[r0][c0];

    while (!pq.empty()) {
        ll cost = pq.top().cost;
        int r = pq.top().row;
        int c = pq.top().col;
        pq.pop();

        if (dist[r][c] < cost) continue;

        for (int d = 0; d < 4; ++d) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (nr < 1 || nr > N || nc < left || nc > right) continue;
            ll nextCost = cost + mmap[nr][nc];
            if (dist[nr][nc] > nextCost) {
                dist[nr][nc] = nextCost;
                pq.push({nextCost, nr, nc});
            }
        }
    }
}

void binarySearch(int left, int right, vector<int> &index) {
    if (left > right || index.empty()) return;
    int mid = (left + right) >> 1;

    for (int r = 1; r <= N; ++r) {
        dijkstra(r, mid, left, right);
        for (auto q:index) {
            queries[q].ans = min(queries[q].ans,
                                 dist[queries[q].from.first][queries[q].from.second] +
                                 dist[queries[q].to.first][queries[q].to.second] - mmap[r][mid]);
        }
    }

    vector<int> leftIndex, rightIndex;
    for (auto i:index) {
        if (queries[i].to.second < mid) leftIndex.push_back(i);
        if (queries[i].from.second > mid) rightIndex.push_back(i);
    }
    binarySearch(left, mid - 1, leftIndex);
    binarySearch(mid + 1, right, rightIndex);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= N; ++i) { // ~5
        for (int j = 1; j <= M; ++j) { // ~100,000
            cin >> mmap[i][j];
        }
    }
    cin>>Q;

    for (int i = 0; i < Q; ++i) { // ~100,000
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        queries[i].constructor(r1, c1, r2, c2);
    }

    vector<int> index(Q);
    for (int i = 0; i < Q; ++i)  // ~100,000
        index[i] = i;

    binarySearch(1, M, index);

    for (int i = 0; i < Q; ++i) { // ~100,000
        cout << queries[i].ans << "\n";
    }
    return 0;
}

SWEA 코드 (C++)

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

typedef long long ll;

int dr[] = {0, 1, 0, -1};
int dc[] = {1, 0, -1, 0};
struct Query {
    int r1, c1, r2, c2;
    ll ans;

    void constructor(int r1, int c1, int r2, int c2) {
        if (r1 > r2) {
            swap(r1, r2);
            swap(c1, c2);
        }
        this->r1 = r1;
        this->c1 = c1;
        this->r2 = r2;
        this->c2 = c2;
        ans = 1e18;
    }
};

struct Node {
    ll cost;
    int r, c;

    bool operator < (const Node &t) const {
        return cost > t.cost;
    }
};

int H, W, Q;
int mmap[10001][4];
ll dist[10001][4];

Query queries[100001];

void dijkstra(int r0, int c0, int beg, int end) {
    for (int i = beg; i <= end; ++i) {
        for (int j = 1; j <= W; ++j) {
            dist[i][j] = 1e18;
        }
    }

    priority_queue<Node> pq;
    pq.push({mmap[r0][c0], r0, c0});
    dist[r0][c0] = mmap[r0][c0];

    while (!pq.empty()) {
        Node node = pq.top();
        pq.pop();

        if (dist[node.r][node.c] < node.cost) continue;

        for (int i = 0; i < 4; ++i) {
            int r = node.r + dr[i];
            int c = node.c + dc[i];
            if (r < beg || r > end || c < 1 || c > W) continue;

            ll cost = node.cost + mmap[r][c];
            if (dist[r][c] > cost) {
                dist[r][c] = cost;
                pq.push({cost, r, c});
            }
        }
    }
}

void binarySearch(int beg, int end, vector<int> &index) {
    if (beg > end || index.empty()) return;
    int mid = (beg + end) >> 1;

    for (int j = 1; j <= W; ++j) {
        dijkstra(mid, j, beg, end);
        for (int i : index) {
            auto &q = queries[i];
            q.ans = min(q.ans, dist[q.r1][q.c1] + dist[q.r2][q.c2] - mmap[mid][j]);
        }
    }

    vector<int> leftIndex, rightIndex;
    for (int i : index) {
        if (queries[i].r2 < mid) leftIndex.push_back(i);
        else if (queries[i].r1 > mid) rightIndex.push_back(i);
    }
    binarySearch(beg, mid - 1, leftIndex);
    binarySearch(mid + 1, end, rightIndex);
}

ll getResult() {
    ll result = 0;
    for (int i = 0; i < Q; ++i) {
        result += queries[i].ans;
    }
    return result;
}

int main(int argc, char **argv) {
    int test_case;
    int T;
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case) {
        cin >> H >> W >> Q;
        for (int i = 1; i <= H; ++i) {
            for (int j = 1; j <= W; ++j) {
                cin >> mmap[i][j];
            }
        }

        for (int i = 0; i < Q; ++i) {
            int r1, c1, r2, c2;
            cin >> r1 >> c1 >> r2 >> c2;
            queries[i].constructor(r1, c1, r2, c2);
        }

        vector<int> indices = vector<int>(Q);
        for (int i = 0; i < Q; ++i) {
            indices[i] = i;
        }

        binarySearch(1, H, indices);

        cout<< "#" << test_case << " " << getResult() << endl;
    }
    return 0;
}

참고문헌

https://david0506.tistory.com/82
https://justicehui.github.io/ps/2019/12/30/BOJ18253/