[백준] 13911번 - 집 구하기 (C++)

• 문제 링크

포스팅 목적

그래프 문제만 주구장창 풀어본 결과, 대부분의 문제는 우선순위 큐를 활용한 다익스트라 알고리즘으로 해결 가능하다. 다익스트라를 적용하고 문제마다 다른 세부적인 조건만 처리해주면 그냥저냥 풀린다.
그런데, 이 문제는 달랐다. 다익스트라 알고리즘에 대해서 좀 더 잘 이해하게 되었다고나 할까... 문제도 억지로 만든 느낌보다는 실용적이어서 재밌었다. 물론 실제로 적용해 보고자 한다면 지도를 모델링 하는 것이 더 어려운 작업일듯하다.

알게 된 것

내 코드도 답을 얻을 수는 있다. 다만 시간초과가 날 뿐... 딱히 획기적인 아이디어 없이 for문만 마구 사용해서 어떻게든 답을 구했다. 모범 답안으로부터 얻은 것들을 정리해 보자.

첫번 째 : 두 정점 사이에 두 개 이상의 간선 처리

그래프의 간선 정보를 입력할 때, 일반적으로 (정점1, 정점2, 가중치)(u, v, w) 와 같은 방식으로 입력한다. 이를 저장하는 방식에는 인접 리스트와 인접 행렬이 있는데, 성능 측면에서 인접 리스트가 훨씬 우월하므로 가급적 인접 리스트를 사용한다. 그런데 문제들 중에 간혹 "두 정점 사이에는 두 개 이상의 간선이 존재할 수 있다." 라는 조건이 있어서 상당히 찝찝하게 만드는 경우가 있다.

항상 최단거리를 구하는 것이 문제이므로 간선이 두 개 이상 있다면 가중치가 더 작은 값으로 저장하면 된다. 근데 이걸 인접 리스트로 처리하려면 간선 하나의 정보를 입력할 때마다, 같은 두 정점을 잇는 간선이 있는지 찾아봐야 한다. 이게 귀찮기도하고 인접 리스트의 좋은 성능 이점을 상쇄시킬 만큼 오버헤드가 크다.

그런데 굳이 여러 간선 중에 가중치가 가장 작은 하나만 골라줄 필요가 없다는 것이 결론이다. 다익스트라 알고리즘은 모든 정점을 순회하면서 각 정점에 연결된 간선을 모두 체크해서 인접한 정점의 최단거리를 갱신한다. 갱신의 조건은 해당 간선으로 이동했을 때 도착한 정점의 거리가 기존에 입력된 거리보다 더 작을 때이다. 따라서 간선이 두 개 이상이라고 해서 인접 리스트를 활용하여 다익스트라 알고리즘을 수행하는데는 전혀 문제가 없다.

물론, 입력 시에 가중치가 가장 작은 간선 하나만 남겨준다면 해당 간선을 체크하는 연산을 줄일 수 있겠지만, 오히려 간선 하나만 남기는 작업이 연산량을 더 필요로 하기 때문에 어리석은 생각이다.

그렇다면 왜 찝찝하게 저런 조건을 주는거지? 인접 리스트를 활용하면 문제가 되지 않지만, 인접 행렬을 사용할 경우에 문제가 생기기 때문이다. 동일한 두 정점을 잇는 간선이 계속해서 주어진다면 인접 행렬에서는 계속 가중치가 덮어쓰기 되어서 가장 마지막에 입력된 정보만이 남게 될 것이다. 그런데 마지막에 입력된 가중치가 최솟값이라고 보장할 수 없으므로 문제가 생긴다. 웬만하면 인접 리스트를 사용하므로 문제가 없었는데.. 혼자 쓸데없는 짓을 하고 있었다. 앞으로는 이 조건이 주어지더라도 찝찝해하지 말자.

두번 째 : 다익스트라 알고리즘의 거리 갱신

문제에서 맥도날드랑 스타벅스가 한 개 였으면 좋겠는데, 여러 개 있다는게 문제다. 내가 짠 코드는 모든 맥도날드와 스타벅스에 대해서 for문을 돌려서 전부 확인 하는 것이었다. 이렇게 하면 맥날과 스벅이 같은 곳에 존재할 수 있으므로, 최악의 경우에 다익스트라 알고리즘을 (V-1)*(V-1)번 돌려야 한다. V의 범위가 10,000까지이므로 1억 번 가까이 수행하는 것이다. 시간초과 나오는 것은 당연하다.

그렇다면 어떻게?
다익스트라 알고리즘이 한 정점에서 시작해야 된다는 고정관념을 버리면 된다. 맥세권인 집을 찾으려면 어떤 맥도날드이든지 간에, 해당 집은 가장 가까운 맥도날드와의 최단거리만 알면 된다. 그래서 모든 맥도날드 노드를 시작점으로 우선순위 큐에 넣어주고 시작하면 된다.

다익스트라는 1번 정점이 시작점일 때, 1번에서 모든 정점으로의 최단거리를 알 수 있다. 그런데 2번에서 3번 정점으로의 최단거리 같은건 알 수가 없다. 이걸 구하려면 2번을 시작점으로 해서 한 번 더 돌려야 된다. 이 때 1번 정점을 시작으로 하여 구한 거리벡터를 다시 사용하면 안 되고, 초기화 된 새로운 거리벡터를 사용해야 한다. 거리벡터를 그대로 사용할 경우, 각 정점은 1번과 2번에서의 최단 거리중 더 작은 값으로 갱신된다.

이 문제의 경우는 특수하게도 여러 시작점 중에서 각 정점으로의 최단거리 중 최솟값을 필요로 하므로 거리벡터를 중복 사용하여 구할 수 있다. 거리벡터를 중복 사용하여 다익스트라 알고리즘을 여러번 수행하든지, 우선순위 큐에 여러 시작점들을 넣고 한 번만 수행하든지 그 결과는 같다. 역으로 생각해보면 모든 집에서 다익스트라를 돌려서 맥도날드로의 최단거리 중에서 최솟값을 그 집에다 써주는거다.

더미 노드라는 개념을 도입할 수도 있는데, 맥도날드들을 가중치 0으로 연결한 시작 노드이다. 이렇게 하면, 여러 개의 시작 노드를 하나의 더미 노드로 묶어주므로 다익스트라의 "한 정점으로부터" 라는 개념과 상응하게 된다. 하지만 주어진 정점 이외의 정점을 추가하는 것이기도 하고, 어차피 더미 노드는 각 시작점들을 우선순위 큐에 넣어주는 역할을 하므로 개념상 이해하는 것은 좋지만 굳이 이렇게 할 필요는 없을 것 같다.

세번 째 : 배열에서 자료의 검색

내가 짠 코드에서는 집인지 아닌지를 확인하기 위해서 isHouse()라는 함수를 정의했다. 스벅, 맥날의 정점 번호가 들어 있는 벡터에 대해서 선형 검색을 수행하여 해당 정점이 집인지 아닌지를 찾아주는 함수이다. 선형 검색은 기본적으로 시간 복잡도 O(n)으로 상당히 느린 연산이다. 오버헤드가 큰 줄 알면서도 달리 방법을 찾지 못했었다.

방법은 스벅, 맥날이 시작점이었다는 것에 착안하는 것이다. 시작점이므로 거리 벡터의 값이 0이다. 이 값을 활용하면 선형 검색을 할 필요없이 인덱스로 바로 알 수 있다. 이미 주어져 있는 값을 활용하는 쪽으로 생각해보려고 노력하자.

내가 짠 저세상 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 100000000
using namespace std;

vector<pair<int, int> > map[10001];
vector<int> dist_m(10001, INF);
vector<int> dist_s(10001, INF);

class Info {
public:
    int node, cost;

    bool operator<(const Info &rhs) const {
        return this->cost > rhs.cost;
    }
};
priority_queue<Info> pq;
priority_queue<Info> res;

bool isHouse(int vertex, vector<int> &mac, vector<int> &star) 
{
    for (int i = 0; i < mac.size(); ++i) {
        if (mac[i] == vertex) return false;
    }
    for (int i = 0; i < star.size(); ++i) {
        if (star[i] == vertex) return false;
    }
    return true;
}

void Dijkstra(int start, bool isMac)
{
    if (isMac) {
        fill(dist_m.begin(), dist_m.end(), INF);
        dist_m[start] = 0;
    } else {
        fill(dist_s.begin(), dist_s.end(), INF);
        dist_s[start] = 0;
    }
    pq.push({start, 0});

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

        for (int i = 0; i < map[node].size(); ++i) {
            int nextNode = map[node][i].first;
            int nextCost = map[node][i].second;
            if (isMac) {
                if (dist_m[nextNode] > dist_m[node] + nextCost) {
                    dist_m[nextNode] = dist_m[node] + nextCost;
                    pq.push({nextNode, dist_m[nextNode]});
                }
            } else {
                if (dist_s[nextNode] > dist_s[node] + nextCost) {
                    dist_s[nextNode] = dist_s[node] + nextCost;
                    pq.push({nextNode, dist_s[nextNode]});
                }
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    int v, e;
    cin >> v >> e;
    for (int i = 1; i <= e; ++i) {
        int u, v, w; cin >> u >> v >> w;
        map[u].push_back(make_pair(v, w));
        map[v].push_back(make_pair(u, w));
    }

    int m, s, x, y;
    cin >> m >> x; vector<int> mac(m+1);
    for (int i = 1; i <= m; ++i) cin >> mac[i];

    cin >> s >> y; vector<int> star(s+1);
    for (int i = 1; i <= s; ++i) cin >> star[i];

    for (int i = 1; i <= m; ++i) {
        Dijkstra(mac[i], true);
        for (int j = 1; j <= s; ++j) {
            Dijkstra(star[j], false);
            for (int k = 1; k <= v; ++k) {
                if (dist_m[k] <= x && dist_s[k] <= y) {
                    res.push({k, x + y});
                }
            }
        }
    }

    while (true) {
        int vertex = res.top().node;
        if (isHouse(vertex, mac, star)) {
            cout << res.top().cost << endl;
            break;
        } else {
            res.pop();
        }
    }

    return 0;
}

모범 답안

#include <iostream>
#include <vector>
#include <queue>
#define INF 100000000
using namespace std;

vector<pair<int, int> > map[10001];
vector<int> dist_m(10001, INF);
vector<int> dist_s(10001, INF);

class Info {
public:
    int node, cost;

    bool operator<(const Info &rhs) const {
        return this->cost > rhs.cost;
    }
};
priority_queue<Info> pq;

void Dijkstra(vector<int> &dist)
{
    while (!pq.empty()) {
        int node = pq.top().node;
        int cost = pq.top().cost;
        pq.pop();
        
        for (int i = 0; i < map[node].size(); ++i) {
            int nextNode = map[node][i].first;
            int nextCost = map[node][i].second;
            if (dist[nextNode] > dist[node] + nextCost) {
                dist[nextNode] = dist[node] + nextCost;
                pq.push({nextNode, dist[nextNode]});
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    int v, e;
    cin >> v >> e;
    for (int i = 1; i <= e; ++i) {
        int u, v, w; cin >> u >> v >> w;
        map[u].push_back(make_pair(v, w));
        map[v].push_back(make_pair(u, w));
    }
    
    int m, x, s, y;
    cin >> m >> x;
    for (int i = 1; i <= m; ++i) {
        int tmp; cin >> tmp;
        dist_m[tmp] = 0;
        pq.push({tmp, 0});
    };
    Dijkstra(dist_m);
    
    cin >> s >> y;
    for (int i = 1; i <= s; ++i) {
        int tmp; cin >> tmp;
        dist_s[tmp] = 0;
        pq.push({tmp, 0});	// <---------- 두번 째
    };
    Dijkstra(dist_s);

    int mini = 2*INF;
    for (int i = 1; i <= v; ++i) {
        if (dist_m[i] && dist_s[i] && dist_m[i] <= x && dist_s[i] <= y) {  // <--- 세번 째
            mini = min(mini, dist_m[i] + dist_s[i]);
        }
    }

    if (mini == 2*INF) cout << -1 << endl;
    else cout << mini << endl;

    return 0;
}