강한 연결 요소(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번으로 해결 가능
다음에는 타잔 알고리즘을 직접 구현해서 비교해 보겠습니다.
'2025 > 알고리즘' 카테고리의 다른 글
백준 - 16287 (0) | 2025.03.27 |
---|---|
백준 - 1086 박상원 (0) | 2025.03.08 |
c++ pow 함수 사용 시 고려해야 할 사항 - BOJ 9527 (0) | 2025.02.06 |