[그래프] [시도x] TPATH 여행 경로 정하기

1. 문제

 

한 도시에서 다른 도시까지 여행을 하고싶다.

 

철도망은 여러 개의 역들과 그들을 잇는 노선으로 구성되어 있다.

 

각 구간별로 철도의 운행 속도가 정해져 있다.

 

 

가속과 감속을 반복하면 멀미때문에 괴롭다.

 

따라서 항상 비슷한 속도로 여행하고싶다.

 

철도망이 주어질때 여행 구간 중

 

최대 운행 속도와 최소 운행 속도의 차를 최소화하는 경로를 찾는 프로그램을 작성하라

 

 

 

시작 철도역은 항상 0 번이고 도착할 철도역은 항상 N-1번이다.

 

 

 

2. 책의 풀이1

 

어떤 경로에서 모든 간선의 가중치가 어떤 값 U이거나 그보다 작을 때, U를 '상한'이라고 하고

반대로 모든 간선의 가중치가 어떤 값 L이거나 그보다 클 때, L을 이 경로의 '하한'이라고 하자.

경로의 최소 상한과 최대 하한의 차이를 경로의 '너비'라고 하면

이 문제는 두 정점을 연결하는 최소 너비 경로를 찾는 문제가 된다.

 

변수를 하나 고정한 형태의 더 단순한 문제를 만들어보자.

경로의 상한과 하한을 동시에 찾는 대신, 하나가 주어질 때 다른 하나를 찾는 문제를 만드는 것이다.

 

minUpperBound(low) = 하한이 low이면서 시작점과 도착점을 연결하는 경로의 최소 상한은?

 

가능한 모든 하한에 대해 위를 수행하고, 그 중 상한과 하한의 최소 차이를 선택하면되는 것이다.

 

minUpperBound()를 이용해 원래 문제를 해결하는 MinWeightDifference()는 다음과 같다.

 

 

여기서 weights는 가중치가 정렬된 목록이다.

const int INF = 987654321;
int V, E;
 
vector<pair<int, int> > adj[MAX_V];
 
vector<int> weights;
 
int minUpperBound(int low);
 
int minWeightDifference()
{
    int ret = INF;
    for(int i = 0; i < weight.size(); i++)
        ret = min(ret, minUpperBound(i) - weights[i]);
    return ret;
}

 

3. 이분 검색과 BFS

 

주어진 하한보다 가중치가 작은 간선들을 제거하면 minUpperBound() 를 쉽게 구현할 수 있다.

 

그러면 문제는 두 정점을 잇는 간선 중 최대 간선의 가중치를 최소화하는 문제로 바뀐다.

 

이 문제는 남극기지문제의 풀이랑 비슷하다.

 

남극 기지 문제를 풀 때 이분 검색과 BFS를 이용하여 문제를 풀 수 있다.

 

사용할 수 있는 최대 가중치에 대해 이분 검색하면서, 각 경우에 모든 정점이 연결되어 있는지 확인하는 것이다.

 

시작점과 도착점이 연결되어 있는지만을 확인하면 같은 방식으로 minUpperBound()를 구현할 수 있다.

 

이 방법은 O(lgE) 번 너비 우선 탐색을 해야하는데, 각 어비 우산 탐색에는 O(V+E)의 시간이 걸리므로

 

minUpperBound()의 시간 복잡도는 O(ElgE)가 된다.

 

전체 시간 복잡도는 여기에 O(E)를 곱한 값이다.

 

코드는 다음과 같다.

bool hasPath1(int lo, int hi)
{
    vector<bool> discovered(V, false);
    queue<int> q;
    discovered[0] = true;
    q.push(0);
 
    while(!q.empty()) 
    {
        int here = q.front();
        q.pop();
        for(int i = 0; i < adj[here].size(); i++)
        {
            int there = adj[here][i].second;
              int dist = adj[here][i].first;
              if(lo<=dist&&dist<=hi&&there == V-1) return true;
            if(!discovered[there]&& lo <=dist && dist <= hi)
            {
                q.push(there);
                discovered[there] = true;
            }
        }
    }
    return false;
}
 
vector<bool> visited;
bool dfs(int here,int lo, int hi) {
  bool ret = false;  
  visited[here] = true;
  if(here == V-1) return true;
  
    for(int i = 0 ; i < adj[here].size(); ++i) {
        int there = adj[here][i].second;
          int cost = adj[here][i].first;
        if(!visited[there] && cost <= hi && lo <= cost)
            ret = (dfs(there, lo, hi)|ret);
    }
  return ret;
}
 
bool hasPath2(int lo, int hi) {
    visited = vector<bool> (V, false);
    return (dfs(0, lo, hi) | false);
}
 
 
int binarySearchMinUpperBound(int low)
{
    int lo = low - 1, hi = weights.size();
    while(lo + 1 < hi)
    {
        int mid = (lo + hi) / 2;
        if(hasPath(weights[low], weights[mid]))
            hi = mid;
        else
            lo = mid;
    }
    if(hi == weights.size()) return INF;
    return weights[hi];
}
 
int minWeightDifference()
{
    int ret = INF;
      for(int i = 0; i < weights.size(); i++)
        ret = min(ret, binarySearchMinUpperBound(i) - weights[i]);
    return ret;
}

 

 

4. 최소 스패닝 트리 알고리즘 변형하기

 

최소 스패닝 트리 알고리즘들의 동작 원리를 이해하고 변형하면 minUpperBound()를 구현할 수 있다.

 

크루스칼과 프림 알고리즘은 모두 가중치가 작은 간선 부터 그래프에 추가하며, 그래프가 전부 연결되면 종료한다.

 

따라서 0~V-1가 연결되는 시점에서 종료하고, 마지막에 추가한 간선의 가중치를 반환하면된다.

 

 

프림 알고리즘을 써서 이 문제를 구현하면 O(ElgV)의 시간안에 minUpperBound()를 구현할 수 있다.

(크루스칼 알고리즘은 O(ElgE))

 

전체 시간 복잡도는 O(E^2lgV)가 되므로 이분 검색 O(E^2lgE) 과 비슷하다.

 

 

그러나 같은 그래프에 대해 크루스칼 알고리즘을 여러 번 수행한다는 사실을 이용하면 더 빠르게 문제를 풀 수 있다.

 

크루스칼 알고리즘의 수행 시간은 간선의 정렬이 지배하는데 이 문제에선 간선이 변화하지 않기 때문에

 

한번만 정렬하면 크루스칼의 시간복잡도는 O(E) 즉. 전체 시간 복잡도는 O(E^2)이 된다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
 
using namespace std;
 
const int INF = 987654321;
const int MAX_V = 2000;
int V, E;
vector<int> weights;
vector<pair<int, pair<int, int> > > edges;
 
struct DisjointSet {
    vector<int> parent, rank;
    DisjointSet(int n) : parent(n), rank(n, 1) {
        for(int i = 0; i < n; i++) 
            parent[i] = i;
    }
    int find(int u) {
        if( u == parent[u]) return u;
        return parent[u] = find(parent[u]);
    }
    void merge(int u, int v) {
        u = find(u); v = find(v);
        if(u == v) return;
        if(rank[u] > rank[v]) swap(u, v);
        parent[u] = v;
        if(rank[u] == rank[v]) rank[v]++;
    }
};
int kruskalMinUpperBound(int low)
{
    DisjointSet sets(V);
    for(int i = 0; i < edges.size(); i++)
    {
        if(edges[i].first < weights[low]) continue;
        sets.merge(edges[i].second.first, edges[i].second.second);
        if(sets.find(0) == sets.find(V-1))
            return edges[i].first;
    }
    return INF;
}
int minWeightDifference()
{
    int ret = INF;
      for(int i = 0; i < weights.size(); i++)
        ret = min(ret, kruskalMinUpperBound(i) - weights[i]);
    return ret;
}
int main()
{
  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  int C;
  cin>>C;
  while(C--)
  {
    cin>>V>>E;
    edges.clear();
    weights = vector<int>(E);
    for(int i = 0; i < E;i++)
    {
      int a, b, c;
      cin>>a>>b>>c;
      edges.push_back(make_pair(c, make_pair(a, b)));
      weights[i] = c;
    }
    sort(edges.begin(), edges.end());
    sort(weights.begin(), weights.end());
    cout<<minWeightDifference()<<"\n";
  }
}

 

 

5. 다른 접근 방법

 

문제를 여러 경우의 수로 쪼갠 뒤 각각을 풀어내는 앞의 접근 방법과는 달리

 

원래 문제를 푸는 단순한 알고리즘을 작성하고

 

이것을 최적화하는 방법으로도 이 문제를 해결할 수 있다.

 

가능한 하한과 상한의 쌍을 하나씩 시험하며 시작점에서 도착점으로 가는 경로가 있는지 확인하는 알고리즘은 다음과 같다.

 

이는 BFS를 O(E^2)번 하므로 전체 시간 복잡도는 O(E^3)이 된다.

 

 

int brute()
{
    int ret = INF;
    for(int lo = 0; lo < weights.size(); lo++)
        for(int hi = lo; hi < weights.size(); hi++)
        {
            if(hasPath(weights[lo], weights[hi]))
            {
                ret = min(ret, weights[hi] - weights[lo]);
                break;
            }
        }
    return ret;
}

 

위 알고리즘은 하한을 하나씩 늘려가며, 각 경우에 가능한 모든 상한을 증가하는 순서대로 시험한다.

 

주목할 부분은 상한 중 일부에 대해서는 경로의 존재를 확인할 것도 없이 경로가 존재하지 않음을 알 수 있다는 점이다.

 

예를 들어 간선들의 가중치가 10, 20, 30, 40, 50 중 하나라고 하자

 

하한이 10일때 최소 상한이 40 이었으면

 

위 코드는 하한을 20으로 두고 다시 수행한다.

 

하한이 10 상한이 40 이라는 말은 하한 10 상한 30을 갖는 경로는 존재하지 않는다는 의미이다.

 

하물며 하한 20, 상한 30을 갖는 경로가 존재할 리 없다는 것이다.

 

 

따라서 이전 하한에 대해 경로가 최초로 존재하는 상한이 얼마인지를 기억해 뒀다가, 하한을 증가시킨 다음에는

 

거기서부터 탐색을 반복하는 최적화를 구현할 수 있다.

 

아래 코드는 개선된 알고리즘의 구현이다.

 

특정 하한에 대해 경로를 찾을 수 없으면 곧장 종료하고, 마지막에 경로를 찾은 상한을 기억해 뒀다가

 

거기에서부터 hi에 대한 반복문을 수행하는 것을 볼 수 있다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
 
using namespace std;
 
const int INF = 987654321;
const int MAX_V = 2000;
int V, E;
vector<pair<int, int> > adj[MAX_V];
vector<int> weights;
 
 
bool hasPath(int lo, int hi)
{
    vector<bool> discovered(V, false);
    queue<int> q;
    discovered[0] = true;
    q.push(0);
 
    while(!q.empty()) 
    {
        int here = q.front();
        q.pop();
        for(int i = 0; i < adj[here].size(); i++)
        {
            int there = adj[here][i].second;
              int dist = adj[here][i].first;
              if(lo<=dist&&dist<=hi&&there == V-1) return true;
            if(!discovered[there]&& lo <=dist && dist <= hi)
            {
                q.push(there);
                discovered[there] = true;
            }
        }
    }
    return false;
}
int optimized()
{
    int ret = INF, foundPathUsing = 0;
    for(int lo = 0; lo < weights.size(); lo++)
    {
        bool foundPath = false;
        for(int hi = foundPathUsing; hi < weights.size(); hi++)
        {
            if(hasPath(weights[lo], weights[hi]))
            {
                ret = min(ret, weights[hi] - weights[lo]);
                foundPath = true;
                foundPathUsing = hi;
                break;
            }
        }
        if(!foundPath) break;
    }
    return ret;
}
 
int main()
{
  int C;
  cin>>C;
  while(C--)
  {
    cin>>V>>E;
    for(int i = 0; i < MAX_V; i++)
      adj[i].clear();
    weights = vector<int>(E);
    for(int i = 0; i < E;i++)
    {
      int a, b, c;
      cin>>a>>b>>c;
      adj[a].push_back(make_pair(c, b));
      adj[b].push_back(make_pair(c, a));
      weights[i] = c;
    }
    sort(weights.begin(), weights.end());
    cout<<optimized()<<"\n";
  }
}

 

6. 훑고 가는 알고리즘

 

hasPath()의 반환 값에 따라 상한을 늘릴지, 하한을 늘릴지가 정해진다는 점을 알게되면

 

좀더 간결하게 코드를 짤 수 있다.

 

가중치의 범위의 양쪽 끝은 weights[]를 훑고 지나간다/

 

 

int optimized()
{
    int lo = 0, hi = 0, ret = INF;
    while(lo < weights.size() && hi < weights.size())
    {
        if(hasPath(weights[lo], weights[hi]))
        {
          ret = min(ret, weights[hi] - weights[lo]);
          lo++;
        }
          else
        {
          hi++;
        }
    }
  return ret;
}

 

- 알고리즘 문제해결전략 981p

 

TPATH