BOJ 2152. 여행 계획 세우기

문제 링크

아이디어 자체는, 그래프의 SCC(Strongly connected components)를 찾아서 전체 개수를 저장하고 각각의 SCC를 정점으로 갖는 새로운 그래프를 만들어서 해결하면 되는 문제일 것 같다는 생각이 들었다!

SCC 찾기

그래프의 SCC를 찾는 방법은 이 블로그를 참고했는데, 나중에 템플릿으로 만들어 두면 좋을 것 같다!

아이디어는 하나의 정점에 대해 DFS를 하되, 방문한 순서를 저장하고 스택에 넣으면서, 방문한 정점이 이미 방문했으나 SCC로 분류되지 않은 정점이면 cycle을 발견한 것이므로 cycle에서 최초로 방문한 정점까지 찾아가 스택에서 값을 빼면서 SCC를 만들어 주는 것이다. 그래서 몇 번째로 방문했는지를 저장하는 visit_order 변수와, DFS에서 어떤 정점을 방문했는지 저장하는 visited 배열과, SCC로 분류되었는지 아닌지를 저장하는 finished 배열이 필요하다.

그러다 보니, BOJ 2150 문제가 SCC를 찾는 문제로 바로 풀려서 같이 풀기로 했다!

위상 정렬된 결과 이용하기

Tarjan의 알고리즘을 이용해 SCC를 생성하는 순서, 즉 finished 배열의 값들은 각각의 SCC로 메타그래프를 생성했을 때 그 메타그래프를 위상 정렬(Topological sort)한 순서의 역순이 된다고 한다. 따라서, 숫자가 클수록(즉 SCC에 나중에 추가되었을수록) 위상 정렬했을 때 앞쪽에 위치한다. 그 이후에, finished[s] 에서 finished[t] 까지 가는 경로 중 가장 많은 도시를 방문하는 경로를 찾으면 된다!

처음에는 그냥 DFS를 하면 최댓값이 찾아지겠지... 하는 생각으로 위상 정렬을 생각하지 않았었는데, 그렇게 되면 발견된 경로가 정말 finished[s] 에서 시작해서 finished[t] 에서 끝나는지 알지 못하게 된다!

따라서 모든 원소가 0으로 초기화된 DP 배열을 이용해, finished[s] 부터 index를 1씩 감소시키며 finished[t] 까지 값을 갱신해주어야 한다.

아이디어는 떠올렸으나 SCC를 찾고 Topological sort를 하는 알고리즘을 배운 지가 오래 되어서 다시 공부할 거리가 많은 문제였다!

어려운 문제였지만, 실제로 여행 계획 세우는 게 나에게는 더 어려울지도...?

// BOJ 2152. 여행 계획 세우기

#include <cstdio>
#include <vector>
#include <set>
#include <stack>

int n, m, s, t;

// Variables for finding SCC of a graph.

// A vector of vector stores SCC of graph.
std::vector<std::vector<int>> sccs;
// A counter variable for storing order of visit and SCC group.
int visit_order {1}; int group_number {0};
// Graph represented by adjacency list.
std::vector<std::vector<int>> graph;
// visited[i] = 0 if not visited, else stores visited order.
std::vector<int> visited;
// Stores if the SCC is determined.
// finished[i] = -1 if not determined, else stores which group vertice i is in.
std::vector<int> finished;
// A stack for finding SCC.
std::stack<int> stack;

// Variables to build a metagraph.
// Each vertex indicates one SCC of original graph.
std::vector<std::set<int>> metagraph;
std::vector<bool> meta_visited;
std::vector<int> scc_size;
std::vector<int> dp;

// Find SCC of a graph using Tarjan's algorithm.
int find_scc(int v) {
    int parent = visit_order;
    visited[v] = visit_order++;
    stack.push(v);
    for (int i: graph[v]) {
        if (visited[i] == 0) {
            parent = std::min(parent, find_scc(i));
        } else if (finished[i] == -1) {
            // Found a cycle.
            parent = std::min(parent, visited[i]);
        }
    }
    // If vertex v is visited first among vertices forming a cycle,
    // pop vertices from stack until v is popped.
    if (parent == visited[v]) {
        std::vector<int> scc;
        while (1) {
            int u = stack.top();
            stack.pop();
            finished[u] = group_number;
            scc.push_back(u);
            if (u == v) break;
        }
        sccs.push_back(scc);
        group_number++;
    }
    return parent;
}

// Traverse DFS and get maximum value.
int dfs(int v, int acc) {
    // Reached to SCC which contains original vertex t.
    if (v == finished[t]) return acc + sccs[v].size();
    int result {0};
    meta_visited[v] = true;
    for (int i: metagraph[v]) {
        if (!meta_visited[i]) {
            result = std::max(result, dfs(i, acc + sccs[v].size()));
        }
    }
    return result;
}

int main() {
    // Input
    scanf("%d %d %d %d", &n, &m, &s, &t);
    s--; t--;
    for (int i=0; i<n; i++) {
        graph.push_back(std::vector<int>());
        visited.push_back(false);
        finished.push_back(-1);
    }
    for (int i=0; i<m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        // Vertex index starts from 1 in the problem.
        x--; y--;
        graph[x].push_back(y);
    }
    // Solve
    // Find SCC of the graph.
    for (int i=0; i<n; i++)
        if (finished[i] == -1) find_scc(i);
    // Build vertices of a metagraph.
    for (int i=0; i<sccs.size(); i++) {
        metagraph.push_back(std::set<int>());
        meta_visited.push_back(false);
        dp.push_back(0);
    }
    // Insert edges to the metagraph.
    for (int i=0; i<n; i++) {
        for (int j: graph[i]) {
            // Edge i -> j in original graph is edge finished[i] -> finished[j] in metagraph.
            if (finished[i] != finished[j]) metagraph[finished[i]].insert(finished[j]);
        }
    }
    // Re-define s and t for being used in metagraph.
    s = finished[s]; t = finished[t];
    // Since we used Tarjan's algorithm,
    // indices of sccs indicates the reversed order of topological sort of metagraph.
    dp[s] = sccs[s].size();
    for (int i=s; i>=t; i--) {
        if (dp[i] == 0) continue;
        for (int j: metagraph[i]) {
            dp[j] = std::max(dp[j], dp[i] + (int)sccs[j].size());
        }
    }
    // Output
    printf("%d\n", dp[t]);
    return 0;
}