2025/알고리즘

코사라주 알고리즘 - BOJ 2150 강한 요소 연결

rimugiri 2025. 2. 7. 23:29
728x90

강한 연결 요소(SCC) 찾기: 유니온 파인드 & 코사라주 알고리즘

이 문제를 해결하는 대표적인 방법은 두 가지가 있습니다.
1️⃣ 타잔(Tarjan) 알고리즘
2️⃣ 코사라주(Kosaraju) 알고리즘

이번 풀이에서는 최종적으로 코사라주 알고리즘을 사용하였습니다.


1. 첫 번째 접근: 유니온 파인드 + DFS

처음에는 위 알고리즘을 알지 못한 상태에서,
🔹 유니온 파인드DFS 탐색을 조합하면 해결할 수 있지 않을까? 🤔 라고 생각했습니다.

✅ 접근 방식

1️⃣ DFS를 이용하여 사이클을 찾는다.
2️⃣ 사이클이 발견되면, 유니온 파인드를 이용해 해당 노드들을 결합한다.
3️⃣ 탐색되지 않은 노드를 찾아 1~2 과정을 반복한다.
4️⃣ 같은 그룹에 속한 노드들을 map을 이용해 관리하고 출력한다.

❌ 실패 원인

이 방식으로 구현했지만, 유니온 파인드 부분에서 역탐색 과정이 포함되면서 시간 초과가 발생했습니다.
결국, 더 효율적인 알고리즘을 찾아보기로 결정했습니다.


📌 코드: 유니온 파인드 + DFS 접근

#include <bits/stdc++.h>

#define FAST std::ios::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL);
typedef long long ll;

using namespace std;

vector<vector<int>> adj;
vector<bool> visited;
vector<int> parent;
vector<int> realVisited;
vector<int> depth;

int V, E;
vector<int> tracer;

int find(int u) {
    if (u == parent[u]) return u;
    return parent[u] = find(parent[u]);
}

void merge(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return;
    if (u > v) swap(u, v);
    parent[v] = u;
}

void dfs(int cur) {
    visited[cur] = true;
    realVisited[cur] = true;
    tracer.push_back(cur);

    for (int next : adj[cur]) {
        if (!visited[next]) {
            depth[next] = depth[cur] + 1;
            dfs(next);
        } else {
            int cycleStartIdx = depth[next];
            for (int i = cycleStartIdx; i < tracer.size() - 1; i++) {
                merge(tracer[i], tracer[i + 1]);
            }
        }
    }

    tracer.pop_back();
    visited[cur] = false;
}

int main() {
    FAST;
    cin >> V >> E;
    adj.resize(V + 1);
    visited.resize(V + 1);
    parent.resize(V + 1);
    realVisited.resize(V + 1);
    depth.resize(V + 1);

    for (int i = 1; i <= V; i++) parent[i] = i;

    for (int i = 0; i < E; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
    }

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

    map<int, vector<int>> cycleGroups;
    for (int i = 1; i <= V; i++) {
        cycleGroups[find(i)].push_back(i);
    }

    cout << cycleGroups.size() << "\n";
    for (auto& cycle : cycleGroups) {
        sort(cycle.second.begin(), cycle.second.end());
        for (int node : cycle.second) {
            cout << node << " ";
        }
        cout << "-1\n";
    }

    return 0;
}
 

2. 최종 해결: 코사라주(Kosaraju) 알고리즘

알고리즘을 찾아보면서, 코사라주 알고리즘이 위상 정렬과 유사하다는 것을 깨달았습니다.
이 알고리즘을 사용하면 효율적으로 강한 연결 요소(SCC)를 찾을 수 있습니다.

❌ 실수했던 부분

처음 구현할 때 DFS 한 번 탐색 후 바로 역방향 DFS(rDFS)를 수행했는데,
이 방식은 1 → 2 → 3 → 1 형태의 사이클과 4 → 2 형태의 단순 연결이 있을 때 문제를 일으켰습니다.

해결 방법:
DFS를 통해 스택에 방문 순서를 저장한 후,
그 순서대로 역방향 DFS를 수행해야 한다는 점을 명확히 이해하고 해결했습니다.


📌 코드: 코사라주 알고리즘

#include <bits/stdc++.h>

#define FAST std::ios::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL);
typedef long long ll;

using namespace std;

vector<int> visited;
vector<int> rvisited;
int V, E;
vector<vector<int>> adj;
vector<vector<int>> radj;
stack<int> s;
vector<vector<int>> scc;

void dfs(int cur) {
    visited[cur] = 1;

    for (auto& next : adj[cur]) {
        if (!visited[next]) dfs(next);
    }

    s.push(cur);
}

void rdfs(int cur) {
    rvisited[cur] = 1;
    scc.back().push_back(cur);
    for (auto& next : radj[cur]) {
        if (!rvisited[next]) rdfs(next);
    }
}

int main() {
    FAST;    
    cin >> V >> E;
    adj.resize(V + 1);
    radj.resize(V + 1);
    visited.resize(V + 1);
    rvisited.resize(V + 1);

    for (int i = 0; i < E; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        radj[b].push_back(a);
    }

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

    while (!s.empty()) {
        int cur = s.top();
        s.pop();
        if (!rvisited[cur]) {
            scc.push_back(vector<int>());
            rdfs(cur);
            sort(scc.back().begin(), scc.back().end());
        }
    }

    cout << scc.size() << '\n';

    sort(scc.begin(), scc.end(), [](vector<int>& a, vector<int>& b) {
        return a[0] < b[0];
    });

    for (int i = 0; i < scc.size(); i++) {
        for (auto& v : scc[i]) {
            cout << v << ' ';
        }
        cout << "-1\n";
    }

    return 0;
}

📌 다음 도전: 타잔(Tarjan) 알고리즘

이번에는 코사라주 알고리즘을 사용했지만,
다음번에는 타잔(Tarjan) 알고리즘을 사용해서 풀어볼 계획입니다. 

코사라주(Kosaraju) vs 타잔(Tarjan)

  • 코사라주는 DFS 2번 사용
  • 타잔은 DFS 1번으로 해결 가능

다음에는 타잔 알고리즘을 직접 구현해서 비교해 보겠습니다.

728x90

'2025 > 알고리즘' 카테고리의 다른 글

백준 - 16287  (0) 2025.03.27
백준 - 1086 박상원  (0) 2025.03.08
c++ pow 함수 사용 시 고려해야 할 사항 - BOJ 9527  (0) 2025.02.06