[백준] 2150번 Strongly Connected Component / Java, Python
Baekjoon Online Judge
algorithm practice
- 단계별 문제풀기
37. 강한 연결 요소
Strongly connected component를 다뤄 봅시다.
1. Strongly Connected Component
Strongly connected component를 다뤄 봅시다.
Strongly connected component를 만들어 봅시다.
이번 문제는 방향 그래프가 주어졌을 때, 그 그래프를 SCC(Strongly Connected Component)들로 나누는 프로그램을 작성하는 문제이다. (방향 그래프의 SCC는 우선 정점의 최대 부분집합이며, 그 부분집합에 들어있는 서로 다른 임의의 두 정점 u, v에 대해서 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재하는 경우를 말한다.)
SCC를 찾는 알고리즘은 크게 이 두가지 방법이다.
- 타잔 알고리즘
모든 정점에 대해 DFS를 수행하여 SCC를 찾는 알고리즘으로, 코사라주 알고리즘에 비해 적용이 더 쉽다고 한다.
① 인접 정점에 방문하며 자기 자신을 스택에 넣고, 재귀적으로 DFS를 수행한다.
② 인접 정점에 방문했지만, 아직 처리중인 상태일 경우, 작은 값으로 부모값을 갱신한다.
③ 부모 노드의 DFS가 끝난 경우에는, 자신의 id값이 스택에서 나올 때까지 스택에 있는 노드들을 pop하고 scc 배열에 추가한다.
④ 만들어진 하나의 scc를 전체 SCC 배열에 추가한다.
(구현이 더 어렵지만, 활용도는 더 높다고 한다.)
- 코사라주 알고리즘
주어진 방향 그래프의 역방향 그래프와 스택을 사용하여 SCC를 구하는 알고리즘이다. 방향, 역방향 그래프가 동일한 SCC를 구성한다는 것을 이용한 방법이다.
① 주어지는 방향 그래프와 그 그래프의 역방향 그래프를 만든다.
② 정점을 담을 스택을 만들고 임의의 정점부터 DFS를 수행한다.
③ DFS가 끝나는 순서대로 스택에 삽입하고, 아직 방문하지 않은 정점에 대해 DFS를 수행한다.
④ 모든 정점이 스택에 담긴 후에는 스택을 pop하여 나오는 정점부터 역방향 그래프에서 DFS를 수행한다.. 이미 방문한 정점은 pop만 시행한다.
⑤ 이때 탐색되는 모든 정점을 SCC로 묶는다.
이것을 스택이 빌 때까지 진행한다.
(타잔 알고리즘에 비해 구현이 더 쉬운 편이라고 한다.)
다음에 더 자세히 정리해봐야 겠다..
Java / Python
- Java
import java.io.*;
import java.util.*;
public class Main {
static int V, E, size, num;
static ArrayList<Integer>[] graph, result;
static int[] order;
static boolean[] visit; // SCC 확정된 정점 확인
static Stack<Integer> stack;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
V = Integer.parseInt(st.nextToken()); // 정점의 개수
E = Integer.parseInt(st.nextToken()); // 간선의 개수
graph = new ArrayList[V + 1];
result = new ArrayList[V + 1];
for (int i = 0; i < V + 1; i++) {
graph[i] = new ArrayList<>();
result[i] = new ArrayList<>();
}
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
graph[a].add(b);
}
order = new int[V + 1];
visit = new boolean[V + 1];
size = 0;
num = 0;
stack = new Stack<>();
for (int i = 1; i < V + 1; i++) {
if (order[i] == 0)
SCC(i);
}
sb.append(size + "\n");
for (int i = 0; i < V + 1; i++) {
int s = result[i].size();
// 2^K 번째 조상 노드 저장
if (s > 0) {
for (int j = 0; j < s; j++) {
sb.append(result[i].get(j) + " ");
}
sb.append("-1\n");
}
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
private static int SCC(int idx) {
order[idx] = ++num;
stack.add(idx);
int root = order[idx];
for (int i = 0; i < graph[idx].size(); i++) {
int temp = graph[idx].get(i);
if (order[temp] == 0)
root = Math.min(root, SCC(temp));
else if (!visit[temp])
root = Math.min(root, order[temp]);
}
if (root == order[idx]) {
ArrayList<Integer> tempArr = new ArrayList<>();
while (true) {
int top = stack.pop();
tempArr.add(top);
visit[top] = true;
if (top == idx)
break;
}
Collections.sort(tempArr);
int min = Collections.min(tempArr);
result[min] = tempArr;
size++;
}
return root;
}
}
- Python
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
V, E = map(int, input().split())
graph = [[] for _ in range(V + 1)]
reverse_graph = [[] for _ in range(V + 1)]
for _ in range(E):
a, b = map(int, input().split())
# 정방향 그래프, 역방향 그래프 추가
graph[a].append(b)
reverse_graph[b].append(a)
# 정방향 dfs, dfs 가 종료되는 노드를 stack에.
def dfs(node, visit, stack):
visit[node] = 1
for now in graph[node]:
if visit[now] == 0:
dfs(now, visit, stack)
stack.append(node)
# 역방향 dfs, 탐색하는 순서대로 stack에.
def reverse_dfs(node, visit, stack):
visit[node] = 1
stack.append(node)
for now in reverse_graph[node]:
if visit[now] == 0:
reverse_dfs(now, visit, stack)
stack = []
visit = [0] * (V + 1)
# 모든 노드에서 dfs를 수행.
for i in range(1, V + 1):
if visit[i] == 0:
dfs(i, visit, stack)
visit = [0] * (V + 1)
result = []
while stack:
# pop되는 요소에서 역방향 dfs, scc를 결과에.
ssc = []
node = stack.pop()
if visit[node] == 0:
reverse_dfs(node, visit, ssc)
result.append(sorted(ssc))
print(len(result))
answer = sorted(result)
for i in answer:
print(*i, -1)
Author And Source
이 문제에 관하여([백준] 2150번 Strongly Connected Component / Java, Python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jini_eun/백준-2150번-Strongly-Connected-Component-Java-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)