그래프 최장거리, 최대이득, 최다비용등

 

최장거리 구하는 문제는 기본적으로 모든 정점을 다 가보고 max값 갱신해주는 형태이다.

백준 10273번 고대동굴탐사 문제처럼 최장거리 뿐 아니라 최대 이득, 최대 비용 이런식으로 비용의 문제로 출제되는 경우도 있다.

한가지 생각할 점은, 모든 정점을 다 가보는 방식이므로 DFS도 효율적이라는 점(BFS를 고집할 필요없다.)

그리고 이문제는 의외로, 방향그래프와 무방향그래프에서의 접근방법이 다른데,

방향그래프에서는 사이클이 없는 DAG이어야 구할 수 있고, 의외로 위상정렬 개념이 들어간다.

위상정렬 개념 없이는 아래와 같은 그래프에서 최장거리 구하기가 까다롭다.

사이클이 존재하는 그래프에서의 최장거리구하기 문제는 NP-Hard에 속하기 때문에PS에서는 안나온다.

모든 정점이 연결되어 있는 완전그래프에서의 최장거리는 TSP문제와 같아진다.

 

무방향 그래프에서도 당연히 사이클이 없는 트리와 같은 형태로만 PS문제로 주어지고, 이경우는 그냥 BFS같은거 돌리면 된다.

(단순 visit처리만 하면 됨)

 

 

사이클없는 무향그래프(트리)에서 최장거리 구하기

기본적으로 트리이거나 포레스트이므로 단순히 BFS돌리면서 max 갱신만 해주면 된다.

이 문제의 답안이기도 하다.

#include <bits/stdc++.h>
using namespace std;
 
using vi = vector<int>;
struct node { int v, w; };
using vvn = vector<vector<node>>;
//모든 노드로의 longest 한번에 구하기
vi longest(int max_v, int start_v, vvn& adj_list, bool base1 = false) {
    if (base1) max_v++;
    vi visit(max_v), max_dist(max_v, -1);
    queue<node> q; q.push({ start_v,0 }); visit[start_v] = 1;
    int ln = -1, ld = 0;
    while (q.size()) {
        node n = q.front(); q.pop();
        if (n.w > max_dist[n.v]) max_dist[n.v] = n.w;
        for (node adj : adj_list[n.v]) {
            if (visit[adj.v])continue; visit[adj.v] = 1;
            q.push({ adj.v, adj.w + n.w });
        }
    }
    return max_dist;
}
//최장경로 길이와 해당노드만 리턴
node longest2(int max_v, int start_v, vvn& adj_list, bool base1 = false) {
    int ln = -1, ld = 0;
    vi md = longest(max_v, start_v, adj_list, base1);
    for (int i = (int)base1; i < (int)base1 + max_v; i++)
        if (i != start_v && md[i] > ld)ld = md[i], ln = i;
    return { ln,ld };  // longest node, longest distance
}
 
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
    //일단 인접리스트 받자
    //V:정점개수
    int V; cin >> V;
    vvn adj_list(V + 1);
    for (int i = 0; i < V - 1; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj_list[u].push_back({ v, w });
        adj_list[v].push_back({ u, w });
    }
    node n1 = longest2(V, 1, adj_list, true);
    node n2 = longest2(V, n1.v, adj_list, true);
    cout << n2.w << endl;
    return 0;
}

트리의 지름을 구하는 문제의 답안이기도 한데, 

트리의 경우는 임의의 점에서 가장 먼 노드(A)를 찾고 그 노드(A)에서 가장 먼 노드까지의 거리가 트리의 지름입니다. 이 그리디 인사이트만 있으면 풀수있다.

 

사이클 없는 유향그래프(DAG)에서 최장거리 구하기

이경우 위상정렬을 해야한다(in_edge처리). 이 문제의 답이기도 하다.

또한 이 코드의 경우 모든 경로에 대한 간선개수를 세는 부분도 있으니 참고하자.

보통은 from[N]배열로 단일경로는 찾을 수 있지만, 여기처럼 모든 경로를 찾으려면 max_dist를 이용한 역 탐색이 필요.

#include <bits/stdc++.h>
using namespace std;
 
struct node { int v, w; };
using vi = vector<int>;
using vvn = vector<vector<node>>;
//모든 노드로의 longest 한번에 구하기
vi visited(10001), max_dist(10001, -1);  // 간선 카운팅 때문에 밖에 나와있다.
vi longest(int max_v, int start_v, vvn& adj_list, vi& in_edge, bool base1 = false) {
    queue<node> q;
    function<void(node)> enqueue = [&](node n) {
        if (in_edge[n.v] != 0) return;
        q.push(n);
    };
 
    //start_v와 무관해도 indgree=0인 정점은 모두 넣어야, 위상정렬이 정상 진행됨
    for (int i = base1; i < max_v + base1; i++) enqueue({ i,0 });
    vi cal(max_v + base1);
    if (start_v == -1)
        for (int i = base1; i < max_v + base1; i++) max_dist[i] = 0, cal[i] = 1;
    else
        max_dist[start_v] = 0, cal[start_v] = 1;
 
    while (q.size()) {
        auto n = q.front(); q.pop();
        for (auto adj : adj_list[n.v]) {
            if (cal[n.v]) //start_v로 부터의 유효한 정점에 대해서만 max 갱신
                max_dist[adj.v] = max(max_dist[adj.v], adj.w + n.w), cal[adj.v]=1;
            in_edge[adj.v]--;
            enqueue({ adj.v, max_dist[adj.v] });
        }
    }
    return max_dist;
}
 
int32_t main()
{
    int n, m; cin >> n >> m;
    vvn adj_list(n + 1), adj_list2(n + 1);
    vi in(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj_list[u].push_back({ v, w }); in[v]++;
        adj_list2[v].push_back({ u, w });
    }
    int s, e; cin >> s >> e;
    vi md = longest(n, s, adj_list, in, true);
    cout << md[e] << endl;
 
    //이제 거꾸로 가면서 간선 개수 카운팅
    set<pair<int, int>> edges;
    queue<node> q; q.push({ e, md[e] });
    vi visited(10001);
    while (q.size()) {
        node n = q.front(); q.pop();
        if (visited[n.v]) continue;
        visited[n.v] = 1;
        if (n.v == s) break;
        for (node adj : adj_list2[n.v]) {
            if (n.w - adj.w == max_dist[adj.v])
                q.push({ adj.v, n.w - adj.w }),
                edges.insert({ min(n.v,adj.v), max(n.v,adj.v) });
        }
    }
    cout << edges.size() << endl;
    return 0;
}

위의 코드를 한층 더 업그레이드(?)해서.. 간선가중치 뿐 아니라 정점가중치도 고려하고, 경로도 구해주는 버전을 만들었다.

이 문제의 답안이기도 하다. 단, 문제특성상 아래코드는 간선가중치는 작을수록 좋고, 정점코스트는 클수록 좋음에 주의

#include <bits/stdc++.h>
using namespace std;
 
const int INF = (int)1e9;
struct node { int v, w; };
using vi = vector<int>;
using vvn = vector<vector<node>>;
//간선가중치(adj_list)뿐 아니라 정점가중치(cost)도 같이 고려.
//모든 노드로의 longest 한번에 구하기, 최장거리와 경로도 같이 리턴해준다.
struct result { vi max_dist; int max_value; vi path; };
result longest(int max_v,int start_v,vvn& adj_list,vi& in_edge,vi& cost,int base1) {
    vi visit(max_v + base1), max_dist(max_v + base1, -INF), from(max_v + base1, INF);
    queue<node> q;
    function<bool(node)> enqueue = [&](node n)->bool {
        if (in_edge[n.v] != 0) return false;
        q.push(n);
        return true;
    };
 
    //start_v와 무관해도 indgree=0인 정점은 모두 넣어야, 위상정렬이 정상 진행됨
    for (int i = base1; i < max_v + base1; i++) enqueue({ i,cost[i] });
    vi cal(max_v + base1);
    if (start_v == -1) 
        for (int i = base1; i < max_v + base1; i++) max_dist[i] = cost[i], cal[i] = 1; 
    else 
        max_dist[start_v] = cost[start_v], cal[start_v] = 1; 
 
    while (q.size()) {
        auto n = q.front(); q.pop();
        for (auto adj : adj_list[n.v]) {
            if (cal[n.v]) //start_v로 부터의 유효한 정점에 대해서만 max 갱신
                max_dist[adj.v] = max(max_dist[adj.v], cost[adj.v] - adj.w + n.w),
                cal[adj.v] = 1;
            in_edge[adj.v]--;
            if (enqueue({ adj.v, max_dist[adj.v] })) from[adj.v] = n.v;
        }
    }
 
    //아래는 좀 비효율적, 위의 복잡도를 높이지 않게 하기위해 걍 놔둠
    int ra = -INF, rb = -1;
    for (int i = base1; i < max_v + base1; i++)
        if (max_dist[i] > ra) ra = max_dist[i], rb = i;
    deque<int> s;
    int ix = rb;
    while (ix != INF)s.push_front(ix), ix = from[ix];
    return { max_dist, ra, vi(s.begin(), s.end()) };
}
 
 
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T; cin >> T; while (T--) {
        int N, E; cin >> N >> E;
        vi cost(N + 1); for (int i = 1; i <= N; i++) { cin >> cost[i]; }
        vector<vector<node>> adj_list(N + 1);
        vi in(N + 1);
        for (int i = 0; i < E; i++) {
            int u, v, w; cin >> u >> v >> w;
            adj_list[u].push_back({ v, w }); in[v]++;
        }
        result r = longest(N, 1, adj_list, in, cost, true);
        cout << r.max_value << ' ' << (int)(r.path).size() << '\n';;
        for (auto a : r.path) cout << a << ' ';
        cout << endl;
    }
    return 0;
}