[백준 10265번] [DFS / SCC] MT

Approach

위 문제에서 나타나게 되는 그래프를 잘 관찰해보면 사이클이 반드시 등장하게 되는 것을 관찰할 수 있다.  즉 1개의 Component를 기준으로 사이클이 존재하고 해당 사이클에 속한 노드를 종점으로 하는 간선을 outdegree로 가지는 노드들이 존재하는 양상을 띄고 있다. 

 

1개의 Component를 기준으로 사이클에 존재하는 것들은 서로서로 순환적으로 요구하고 있으므로 모두 다 버스에 타거나 전부 타지 말아야 한다. 따라서 해당 특성을 잘 고려하면 해당 component에서 버스를 탈 수 있는 인원은 사이클에 속한 사람 ~ 해당 component에 속한 사람이 된다.

 

그리고 최대 인원이 k명이라는 점을 잘 생각해보면 0/1 knapsack 문제와 비슷한 점을 발견할 수 있다. 왜냐하면 해당 component를 추가하기 위해서는 적어도 사이클에 속한 사람이 들어가야하는데 이를 더해서 k를 넘게 되면 해당 component를 추가할 수 없고, k를 넘지 않는다면 무조건 넣을 수 있기 때문이다. 

 

dp[i][j] : 무조건 j명 이상이 타야하는 상황일 때, 버스에 탈 수 있는 사람의 최대값 (단, i번째 component까지 고려)

(Knapsack DP에서 cost를 이 문제에서는 무조건 타야하는 사람의 인원수로 바꿔주면 된다는 아이디어에서 착안하였다.)

 

# Case 1 : dp[i][j] = dp[i - 1][j] (j < comp[i].first) (단, comp[i] = i번째 component의 버스를 탈 수 있는 인원의 최소값과 최대값을 pair값으로 가지고 있는 값)

# Case 2 : dp[i][j] = min(k, max(dp[i - 1][j - comp[i].first] + comp[i].second, dp[i - 1][j])) ( comp[i].first $\le$ j $\le$ k)

 

다만, 이렇게 DP로 풀기 위해서는 각 component 별로 사이클에 속한 인원 수와 component에 속한 인원수를 모두 구할 수 있어야 한다.

총 2가지 접근 방법으로 해결하였는데, 각각의 접근방법은 코드를 보면서 설명하도록 하겠다.

Code 1

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
typedef pair<int, int> pii;

int n, k;
int visited[1001];
int finished[1001];
vector<vector<int> > r(1001);
int r_o[1001];
int cycle_count;
vector<pii> cycle_store;
bool flag;
int dp[1001][1001];

int dfs(int x){
    visited[x] = 1;
    int result = 0;
    for(int i = 0; i < r[x].size(); i++){
        int to = r[x][i];
        if(!visited[to]) result += dfs(to);
        else{
            if(!finished[to]){
                flag = true;
                for(int i = x; i != to; i = r_o[i]){
                    cycle_count++;
                }
                cycle_count++;
            }
        }
    }
    finished[x] = 1;
    return result + 1;
}

int main(void){
    fastio;
    memset(visited, 0, sizeof(visited));
    memset(finished, 0, sizeof(finished));
    memset(dp, 0, sizeof(dp));
    cin >> n >> k;

    for(int i = 1; i <= n; i++){
        int t;
        cin >> t;
        r_o[i] = t;
        r[t].push_back(i); // Edge reversal (Using scc property)
    }
    if(n == k){
        cout << n << "\n";
        return 0;
    }

    for(int i = 1; i <= n; i++){
        if(!visited[i]){
            cycle_count = 0;
            flag = false;
            int component_num = dfs(i);
            int cycle_num = cycle_count;
            if(!flag){
                memset(visited, 0, sizeof(visited));
                memset(finished, 0, sizeof(finished));
            }
            else{
                if(cycle_num <= k){
                    cycle_store.push_back(make_pair(cycle_num, component_num));
                }
            }
        }
    }

    // 가능한 케이스가 없는 경우
    if(cycle_store.empty()){
        cout << 0 << "\n";
        return 0;
    }

    for(int i = cycle_store[0].first; i <= k; i++){
        dp[0][i] = min(k, cycle_store[0].second);
    }
    
    for(int i = 1; i < cycle_store.size(); i++){
        for(int j = 0; j < cycle_store[i].first; j++){
            dp[i][j] = dp[i - 1][j];
        }
        for(int j = cycle_store[i].first; j <= k; j++){
            dp[i][j] = min(k, max(dp[i - 1][j], dp[i - 1][j - cycle_store[i].first] + cycle_store[i].second));
        }
    }

    int result = -1;

    for(int i = 0; i <= k; i++){
        result = max(result, dp[cycle_store.size() - 1][i]);
    }
    cout << result << "\n";
    return 0;
}

맨 처음 방법은 주어진 간선들의 시점과 종점을 바꾸게 되면, 기존의 모든 간선에서 1개씩 outdegree가 있었으므로 모든 노드들의 indegree가 적어도 1개 이상 발생하게 된다. 따라서 cycle을 기준으로 모든 간선을 dfs를 통해 방문할 수 있게 된다.

 

사이클을 발견하게 되면 visited와 finished 배열을 초기화한 후 사이클에 속한 원소 중 1개를 dfs의 루트 노드로 제공하여 component 안에 속한 노드들의 개수를 세어주었다. 이 과정에서 단순히 초기화히여도 되는지에 대한 의구심을 제기할 수 있으나, 1개의 component를 기준으로 방문할 수 있는 모든 정점들을 방문하므로 다른 component를 연산할 때 영향을 끼치지 않으므로 일반성을 잃지 않는다고 할 수 있겠다. (참고 : https://everenew.tistory.com/145)

[백준] No.10265 - MT (C++, SCC, Knapscak)

Code 2

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
typedef pair<int, int> pii;

int n, k;
int dp[1001][1001];
int visited[1001];
int finished[1001];
bool in_cycle[1001];
int r[1001];
int comp_cnt;

vector<pii> comp_store;

int dfs(int x){
    visited[x] = 1;
    int to = r[x];
    if(!visited[to]) dfs(to);
    else{
        if(finished[to] == -1){
            for(int i = to; i != x; i = r[i]){
                in_cycle[i] = true;
            }
            in_cycle[x] = true;
            return finished[x] = comp_cnt++;
        }
    }
    return finished[x] = finished[to];
}

int main(void){
    fastio;
    memset(visited, 0, sizeof(visited));
    memset(finished, -1, sizeof(finished));
    memset(in_cycle, 0, sizeof(in_cycle));
    memset(dp, 0, sizeof(dp));
    cin >> n >> k;

    for(int i = 1; i <= n; i++){
        int t;
        cin >> t;
        r[i] = t;
    }

    for(int i = 1; i <= n; i++){
        if(!visited[i]){
            dfs(i);
        }
    }
    
    comp_store = vector<pii> (comp_cnt, make_pair(0, 0));

    for(int i = 1; i <= n; i++){
        if(in_cycle[i]){
            comp_store[finished[i]].first++;
            comp_store[finished[i]].second++;
        }
        else comp_store[finished[i]].second++;
    }

    if(comp_store[0].first <= k){
        dp[0][comp_store[0].first] = min(k, comp_store[0].second);
    }
    
    for(int i = 1; i < comp_store.size(); i++){
        for(int j = 0; j < comp_store[i].first; j++){
            dp[i][j] = dp[i - 1][j];
        }
        for(int j = comp_store[i].first; j <= k; j++){
            dp[i][j] = min(k, max(dp[i - 1][j], dp[i - 1][j - comp_store[i].first] + comp_store[i].second));
        }
    }

    int result = -1;

    for(int i = 0; i <= k; i++){
        result = max(result, dp[comp_store.size() - 1][i]);
    }
    cout << result << "\n";
    return 0;
}

다음은, 어떤 노드에서 시작하든 무조건 사이클을 마주할 수 밖에 없다는 특성을 활용해준 것이다.

finished 배열을 component index에 해당하는 내용을 저장하게끔 하는 컨테이너로 사용해주면 된다. 따라서 방문할 수 있든, 방문할 수 있지 않든 finished배열을 가려는 방향의 정보를 그대로 가져와 저장해주면 된다.

 

이 부분때문에 상당히 어려웠다~