[S1] 1325. 효율적인 해킹

https://www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

문제를 푸는데 헷갈리면서 어려웠다. 시간 제한을 먼저 봐야 한다. 5초라는 시간이 주어져 감이 잡히지 않았다. 어느정도로 해야 시간제한이 걸리지 않을까. 그러다 질문 게시판을 봤다... 솔직히 내가 못 푼 문제이다. 생각은 했었다. N번 bfs를 돌려보자라는 생각을 말이다. 하지만, 아무리 생각해도 시간제한이 넘어버릴것 같고, 더 효율적으로 할 수 있는 방법이 있을 것 같아 시도해보지 않았다. 한 번 시도해볼 걸 그랬다. 

나는 이미 풀이법을 말했다. N번 bfs를 돌리면 된다고, 그리고 관계가 있는 노드의 개수를 구한 뒤, 마지막에 가장 많이 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력하면 된다. 

시간이 무료 3800ms가 나오게 된다. 그래서 나는 다른 사람의 코드를 확인했다. 이상한 알고리즘을 사용한 것 같다. 이전에 대회 문제를 해결했을 때도 자주 본 알고리즘이었다. SCC알고리즘이다. 이번 기회에 나도 SCC알고리즘을 공부하고 여기에 적용해보는 기회가 되었다. 이번 블로그를 통해 SCC알고리즘에 대해 공부해보려 한다.

 

방법 1. N번 bfs

방법 2. SCC알고리즘

 

방법 1. N번 bfs

말 그대로 N번 bfs를 진행하여 1 ~ N번 노드가 각각 몇개의 노드에 방문할 수 있는지 bfs를 통해 알아내고, 저장하면 되는 것이다. 코드는 다음과 같다.

#include <cstdio>
#include <vector>
#include <iostream>

std::vector<int> P[10001];
bool V[10001]{};
int cnt[10001]{};

void dfs(int node, int start) {
    V[node] = true;
    cnt[start]++;
    for (auto it : P[node]) {
        if (!V[it]) dfs(it, start);
    }
}

int main(void) {
    std::cin.tie(0); std::cout.tie(0);
    std::ios_base::sync_with_stdio(false);
    int N, M, A, B; std::cin >> N >> M;
    while (M--) {
        std::cin >> A >> B;
        P[B].push_back(A);
    }

    for (int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) V[j] = false;
        dfs(i, i);
    }
    int max = 0;
    for (int i = 1; i <= N; i++) {
        if (max < cnt[i]) max = cnt[i];
    }
    for (int i = 1; i <= N; i++) {
        if (max == cnt[i]) std::cout << i << ' ';
    }
}

어라. dfs로 해결했네. bfs나 dfs나 모든 노드를 방문하는 것이기 때문에 시간 차이는 별로 없다.

 

방법 2. SCC알고리즘

이 문제 때문에 SCC알고리즘 글을 작성했다. 그 글을 참고하고 문제를 보면 좋을 것 같다. 그리고, 이 문제는 SCC를 활용한 응용 문제이기 때문에 개인적으로 SCC에 대한 정확한 이해가 필요한 문제라고 생각한다. 만약 시간제한이 없었더라면 난이도가 매우 높은 문제라고 생각한다.

https://jhcard.tistory.com/197

[알고리즘] SCC 알고리즘

이 문제는 SCC를 알아도 후속 조치가 필요하다. SCC를 이용해 연결 된 노드의 개수를 전부 구하고, 연결된 노드의 수가 가장 많은 SCC그룹을 찾아, 그 그룹에 속하는 노드의 값을 출력해야 한다.

코드를 보면서 알아보자.

우리는 SCC알고리즘을 이용해 특정 노드가 어떤 SCC그룹에 속하는지 nsid라는 SCC id배열을 생성하여 부여해준다. 그리고 우리는 그 id에 속하는 노드가 몇개 있는지 저장할 배열도 필요하다. 그 변수가 cntsid가 된다.

SCC는 강한 연결 요소를 의미한다. 그러니까 SCC로 이루어진 노드들은 서로 연결되어 이동할 수 있는 경로가 된다. 만약 2번이라는 SCC그룹에 속하는 노드가 7개가 있다면 여기에 있는 7개의 노드들은 6개 이상의 노드에 이동할 수 있게 된다. 

왜 이상이라는 표현을 했냐하면 일방적인 방향으로 다른 SCC로 갈 수 있다면 그것도 포함해야 하기 때문이다.

 

자 이것을 알기 위해 SCC를 구한 것과 별개로 SCC에서 다시 한번 dfs를 통해 어디로 이동할 수 있는지 알아내야 한다.

특정 SCC에서 다른 SCC로 갈 수 있는 경로가 있다면 그 SCC끼리의 그래프를 얻어낼 수 있다. 그 변수가 std::vector<int> SCC가 된다. 이 SCC변수를 통해 다른 SCC로 갈 수 있는 경로를 찾고, dfs를 이용해 그 SCC의 개수를 반환하여 갈 수 있는 경로를 구한 뒤, 최대 값을 구하면 되는 것이다.

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>

std::vector<int> c[10001], SCC[10001];
std::stack<int> s;
int cid[10001], id, nsid[10001], sid, cntsid[10001], D[10001];
bool isChild[10001];

inline int dfs(int node) {
    cid[node] = ++id;
    s.push(node);

    int ret = cid[node];
    for (int next : c[node]) {
        if (!cid[next]) ret = std::min(ret, dfs(next));
        else if (!nsid[next]) ret = std::min(ret, cid[next]);
    }

    if (ret == cid[node]) {
        sid++;
        while (true) {
            int t = s.top();
            s.pop();
            nsid[t] = sid;
            cntsid[sid]++;
            if (cid[t] == ret) break;
        }
    }
    return ret;
}

inline int dfs2(int idx, bool visited[]) {
    visited[idx] = true;
    int ret = cntsid[idx];
    for (int cost : SCC[idx]) {
        if (!visited[cost]) ret += dfs2(cost, visited);
    }
    return ret;
}

int main(void) {
    int N, M, A, B; scanf("%d %d", &N, &M);
    while (M--) {
        scanf("%d %d", &A, &B);
        c[B].push_back(A);
    }

    for (int i = 1; i <= N; i++) {
        if (!cid[i]) dfs(i);
    }

    for (int i = 1; i <= N; i++) {
        for (int next : c[i]) {
            if (nsid[i] != nsid[next]) SCC[nsid[i]].push_back(nsid[next]);
        }
    }

    for (int i = 1; i <= sid; i++) {
        std::sort(SCC[i].begin(), SCC[i].end());
        SCC[i].erase(std::unique(SCC[i].begin(), SCC[i].end()), SCC[i].end());

        for (int node : SCC[i]) isChild[node] = true;
    }

    int imax = 0;
    for (int i = 1; i <= sid; i++) {
        bool visited[10001]{};
        if (!isChild[i]) {
            imax = std::max(imax, D[i] = dfs2(i, visited));
        }
    }

    for (int i = 1; i <= N; i++) {
        if (D[nsid[i]] == imax) printf("%d ", i);
    }
}