[BOJ] 2152번: 여행 계획 세우기

2152번: 여행 계획 세우기

제한 조건
- 시간 제한 : 2s
- 공간 제한 : 128MB

풀이 사용 
- 사용 언어 : C++17
- 사용 시간 : 640ms
- 사용 공간 : 15680KB

풀이 설명
- 플레3 문제 너무 어렵다.
- directed cyclic graph를 SCC(Strongly Connected Components)로 묶어 DAG(Directed Acyclic Graph)로 바꾼다.
- 이후 DAG에서 시작 SCC부터 끝 SCC까지 가는 여러 경로가 있을수 있으니 DP를 이용하여 최대값을 구한다.
- DP[i] : 시작점부터 i번째 SCC까지 거칠수있는 최대도시개수. ( u -> v 일때, DP[v] = DP[u] + sizeofscc[v] )
- SCC를 만드는 방법은 Kosaraju's Algorithm과 Tarjan's Algorithm이 있는데 수업시간에 배운 Kosaraju's Algorithm을 사용하였다. (둘다 O(V+E)인데 Targan이 조금더 빠르다고 함)

#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int vtxCnt; // vertex count
int edgCnt; // edge count
int strVtx; // start vertex
int endVtx; // end vertex

vector<vector<bool>> edge_matrix; // edge adjacency metrix
vector<pair<int, int>> edge_list; // edge adjacency list

vector<char> color; // 방문 기록용 색깔
int time;           // 시간 기록용 timer

vector<int> stack;              // scc 계산용 위상정렬 stack
vector<int> scc;                // Strongly Connected Components
vector<int> sscc;               // Size of SCC
vector<set<int>> scc_edge_list; // SCC edge list
vector<int> dp;                 // 시작지점에서 n번째 scc까지의 최대도시개수

void DFS_visit(int u)
{
    color[u] = 'G'; // Gray
    for (int v = 1; v <= vtxCnt; v++)
        if (edge_matrix[u][v] == true && color[v] == 'W')
            DFS_visit(v);

    color[u] = 'B'; // Black
    stack.push_back(u);
}

void DFS_invert_visit(int u)
{
    color[u] = 'G'; // Gray
    scc[u] = time;
    sscc[time]++;

    for (int v = 1; v <= vtxCnt; v++)
        if (edge_matrix[v][u] == true && color[v] == 'W')
            DFS_invert_visit(v);

    color[u] = 'B'; // Black
}

void calculateDP(int u)
{
    color[u] = 'B';
    for (int v : scc_edge_list[u])
    {
        if (v == u)
            continue;
        else
        {
            int temp = dp[u] + sscc[v];
            if (temp > dp[v])
            {
                dp[v] = temp;
                calculateDP(v);
            }
        }
    }
}

int main(int argc, char const *argv[])
{
#pragma region 입력부
    scanf("%d %d %d %d\n", &vtxCnt, &edgCnt, &strVtx, &endVtx);
    edge_matrix = vector<vector<bool>>(vtxCnt + 1, vector<bool>(vtxCnt + 1, false));

    for (int i = 0; i < edgCnt; i++)
    {
        int a, b;
        scanf("%d %d\n", &a, &b);
        edge_matrix[a][b] = true;
        edge_list.push_back({a, b});
    }
#pragma endregion

#pragma region 깊이우선탐색으로 순방향 DFS 스텍 계산
    time = 0;
    color = vector<char>(vtxCnt + 1, 'W'); // White

    // 목적지에 도달 가능여부 검사
    DFS_visit(strVtx);
    if (color[endVtx] == 'W')
    {
        printf("0");
        return 0;
    }
    // 나머지 위치 DFS 검사
    for (int u = 1; u <= vtxCnt; u++)
        if (color[u] == 'W')
            DFS_visit(u);
#pragma endregion

#pragma region 반전트리를 이용하여 SCC 계산후 그룹화 'Kosaraju Algorithm'..
    time = 0;
    color = vector<char>(vtxCnt + 1, 'W'); // White
    scc = vector<int>(vtxCnt + 1, -1);
    sscc.push_back(0);
    while (!stack.empty())
    {
        int u = stack.back();
        if (color[u] == 'W')
        {
            time++;
            sscc.push_back(0);
            DFS_invert_visit(u);
        }
        stack.erase(stack.end() - 1);
    }

    scc_edge_list = vector<set<int>>(sscc.size(), set<int>());
    for (pair<int, int> p : edge_list)
        scc_edge_list[scc[p.first]].insert(scc[p.second]);
#pragma endregion

#pragma region 'DP'를 이용하여 최대 도시개수 산출
    color = vector<char>(sscc.size(), 'W'); // White
    dp = vector<int>(sscc.size(), 0);
    dp[scc[strVtx]] = sscc[scc[strVtx]];
    calculateDP(scc[strVtx]);
    printf("%d", dp[scc[endVtx]]);
#pragma endregion

    return 0;
}