티스토리 뷰
오늘 코테 문제를 풀다 방향이 있는 그래프에서 Loop의 유무를 검증해야 하는 문제를 만났습니다.
늘 어렴풋이 만 알고 있던 SCC와 WCC에 대해 정리해 보고 공부하기로 했습니다.
SCC ( Strongly Connected Components )
이는 방향성이 있는 그래프에서 출발점과 도착점이 같아지는 경우를 의미합니다. 백문이 불여일견 그림을 보면 바로 알 수 있습니다.
위와 같은 그래프에서 2 - 3 - 4 - 2 으로 2번에서 시작에서 2번으로 도착하는 경우 SCC라고 합니다. 물론 3 - 4 - 3 도 SCC라고 할 수 있습니다.
알고리즘
SCC를 출발점과 도착점이 같아지는 경우 라고 설명한 이유는 알고리즘을 구현할 때 가장 포인트가 되는 조건이라고 생각하기 때문입니다.
위 문장은 탐색 중 방문한 점을 또 방문함 이라고 생각할 수 있습니다. 즉 탐색한 정점들을 기록하면서 탐색하다 이미 방문한 정점에 재방문했을 때 이는 SCC가 존재하는 것이며, SCC의 요소들은 기록 중인 정점에서 재방문한 정점을 통해서 찾을 수 있습니다.
출발 정점은 탐색을 통해 도달하지 못한 정점들만 출발점의 후보로 넣어주면 됩니다.
package Graph.loop;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class DirectGraphLoopFind {
static int n;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
n = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
List<List<Integer>> map = new ArrayList<>();
for (int i = 0; i <= n; i++) {
map.add(new ArrayList<>());
}
for (int i = 0; i < v; i++) {
st = new StringTokenizer(bf.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
map.get(start).add(end);
}
boolean[] visit = new boolean[n + 1];
// 모든 노드에 대해 DFS 호출
for (int i = 1; i <= n; i++) {
if (!visit[i]) {
List<Integer> path = new ArrayList<>();
boolean foundLoop = DFS(map, visit, i, path);
if (foundLoop) {
// 출력 형식에 맞게 경로 출력
for (int node : path) {
System.out.print(node + " ");
}
System.out.println();
}
}
}
}
public static boolean DFS(List<List<Integer>> map, boolean[] visit, int now, List<Integer> path) {
if (visit[now]) {
// 이미 방문한 노드인 경우, 현재 경로에서 루프를 찾음
path.add(now);
return true;
}
visit[now] = true;
path.add(now);
for (int next : map.get(now)) {
if (DFS(map, visit, next, path)) {
return true;
}
}
// DFS가 종료되면 해당 노드를 경로에서 제거
path.remove(path.size() - 1);
return false;
}
}
위 사실 알고리즘은 그럴 듯 해보이지만 문제가 많습니다. ㅠ ...
1. 이미 방문한 노드인 경우 SCC를 생성이라는 조건
위와 같은 경우 SCC는 2 3 4 이지만, 위 알고리즘은 3번 탐색이 끝나는 순간 2 3을 만들고, 4번은 따로 SCC 집합을 생성합니다.
2. 단일 노드로 이루어지는 SCC는 탐색하지 못한다.
SCC를 구하는 알고리즘은 따로 타잔의 강결합 요소(Tarjan's Strongly Connected Components, SCC)라는 알고리즘이 존재합니다.
타잔 강결합 요소 알고리즘
타잔 강결합 알고리즘을 이해..아니 사용이라도 할 수 있기 위해서 탐색 중 SCC 결정 조건에 대한 이해가 필요합니다. SCC가 결정되는 노드는 자신의 자식 노드와 자신의 부모노드가 연결되어 있지 않는 노드입니다.
위 그래프를 보면 2번 노드의 부모 노드는 1번 노드 입니다. 이 1번 노드는 2번의 자식 노드인 3,4번 노드에서 도달할 수가 없습니다. 그림으로 보니까 생각보다 간단한 조건 같아 좀 섭섭하네요. 하지만 이 조건을 어떻게 코드로 타잔님이 만드셨을까요?
부모와 자식 같은 조건을 사용하기 위해서는 우선 탐색의 순서가 기록되어져야 합니다.
현재 1번 정점에서 시작해서 깊이 우선 탐색으로 1, 2, 4, 3번까지 진행한 상황입니다. 이제 3번 노드에서 2번 노드로 갈 준비를 하는데, 2번 노드는 이미 방문한 노드입니다.(이에 대해서는 dis 배열의 초기값 비교를 통해서 확인) 이러한 경우에 3번 노드에 진행 값을 2번 노드의 값인 2로 업데이트 합니다. 이때 2번 노드가 이미 SCC를 이루고 있는지도 확인해야 합니다.
그러면 이제 3번 노드에서 4번 노드로 탐색이 이뤄집니다. 하지만 4번도 이미 방문한 노드이며 4번의 값을 그대로 3번 값으로 덮어쓰면 안 됩니다. 두 값 사이 더 작은 값(= 더 부모님 같은..?)으로 설정해줘야 합니다.
그리고 3번의 탐색 결과값을 반환하여 4번 정점의 값과 비교하여 더 작은 값으로 4번 값을 경신시킵니다. 여기서 설명이 좀 헐렁해진 것 같은데.. 설명을 좀 구체적으로 해보겠습니다.
현재 그림판으로 분홍색으로 표시한 숫자는 각 정점의 탐색 순서 값입니다. 그리고 그 외 색으로 표시된 값은 연결된 부모 노드의 탐색 순서 값입니다. 그리고 연결된 부모 노드의 탐색 순서 값은 각 탐색이 끝날 때 반환합니다. 즉 3번 노드의 탐색이 끝난경우 연결된 부모 노드의 탐색 순서 값인 2를 반환하고, 이를 4번 노드의 탐색 순서 값과 비교를 통해 더 작은 값으로 갱신시켜 줍니다.
그러면 2번 탐색에서는 연결된 부모 노드의 탐색 순서 값 과 정점의 탐색 순서 값이 같아지며 이는 앞서 말한 SCC의 결정 조건인 자신의 자식 노드와 자신의 부모노드가 연결되어 있지 않는 노드를 의미하게 됩니다.
스택이나 List를 사용하여 이제 상황에 적합하게 구현하면 됩니다.
바로 문제를 하나 풀어보겠습니다.
백준 2150번 Strongly Connected Component
https://www.acmicpc.net/problem/2150
문제가 너무 SCC를 구하는 문제네요.
특이점은 SCC 요소들을 정렬하면서 또 SCC 리스트들을 정렬하여 출력하는 형식이 있습니다.
아래 코드입니다.
package Graph.SCC;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Num2150Strongly_Connected_Component {
static int n,v,count,numberOfScc;
static int[] dis;
static boolean[] isSCC;
static Stack<Integer> stack;
static List<List<Integer>> map;
static List<Scc> answer;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
// 1.setUp
n = Integer.parseInt(st.nextToken());
v = Integer.parseInt(st.nextToken());
map = new ArrayList<>();
answer = new ArrayList<>();
for(int i=0;i<=n;i++){
map.add(new ArrayList<>());
}
for(int i=0;i<v;i++){
st = new StringTokenizer(bf.readLine());
map.get(Integer.parseInt(st.nextToken())).add(Integer.parseInt(st.nextToken()));
}
dis = new int[n+1];
isSCC = new boolean[n+1];
stack = new Stack<>();
count = 0;
numberOfScc = 0;
// 2.search
for(int i=1; i<=n;i++){
if(!isSCC[i]){
DFS(i);
}
}
// 3.answer
System.out.println(numberOfScc);
Collections.sort(answer);
for(int i=0;i<numberOfScc;i++){
StringBuilder sb = new StringBuilder();
for(int value : answer.get(i).get()){
sb.append(value).append(" ");
}
System.out.println(sb);
}
}
public static int DFS(int now){
dis[now] = ++count;
stack.push(now);
int momDis = dis[now];
for(int next : map.get(now)){
if(dis[next]==0) momDis = Math.min(momDis,DFS(next));
if(!isSCC[next]) momDis = Math.min(momDis,dis[next]);
}
if(momDis == dis[now]){
numberOfScc++;
Scc scc = new Scc();
while(true){
int popInt = stack.pop();
isSCC[popInt] = true;
scc.add(popInt);
if(popInt == now) break;
}
scc.sort();
scc.add(-1);
answer.add(scc);
}
return momDis;
}
private static class Scc implements Comparable<Scc>{
private final List<Integer> numbers;
Scc(){
numbers = new ArrayList<>();
}
public void sort(){
Collections.sort(numbers);
}
public void add(int value){
numbers.add(value);
}
public List<Integer> get(){
return numbers;
}
@Override
public int compareTo(Scc o){
return numbers.get(0) - o.numbers.get(0);
}
}
}
강한 연결 요소 추출 알고리즘 (Strongly Connected Component)
방향성이 존재하는 유향 그래프에서 그룹 내의 모든 정점이 다른 모든 정점들에 대하여 방문할 수 있는 경우에 그 그룹이 강하게 연결되었다고 하고, 이것을 강한 연결 요소 혹은 강한 결합 요
velog.io
'어차피 공부는 계속 해야한다 너 임마 > 알고리즘' 카테고리의 다른 글
| 밸만 포드 알고리즘과 다이젝스트라 알고리즘 (2) | 2024.10.15 |
|---|---|
| 코사라주 알고리즘 - SCC 알고리즘 (0) | 2024.08.06 |