[1. 개요]
SCC 의 특성
- 방향 그래프에서 정의 된다.
- 같은 SCC 에 속한 노드들은 Cycle 을 형성한다.
=> 같은 SCC 에 속한 노드 간 경로는 반드시 존재한다. - SCC 를 연결하는 간선들을 모으면 DAG 를 형성한다.
SCC 를 응용한 문제
- SAT
SCC 를 찾는데 사용되는 알고리즘은 아래와 같이 크게 두가지가 있다.
- 타잔 알고리즘
=> 시간 복잡도 O(V+E) - 코사라주 알고리즘
타잔 알고리즘은 한번의 DFS 를 통해 모든 SCC 를 찾을 수 있다.
따라서 타잔 알고리즘의 구현 패턴을 익히도록 한다.
- dfsAll 을 수행한다.
- 각 dfs 는 프로토 타입은 아래와 같이 작성하며, 동작은 아래와 같다.
# int dfs(u int), u 에서 dfs 수행 시 가장 먼저 방문 한 방문 순서를 반환,
dfs 동작
- 이번에 방문 한 정점(u) 의 방문 순서를 기록 한다.
=> 1 부터 할당한다. - 이번에 방문 한 정점을 Stack 에 푸쉬한다.
- 인접한 노드들을 체크하여 상황에 맞는 동작을 수행한다. (핵심은 최소 방문 순서 업데이트)
#01. 아직 방문하지 않은 경우,
=> dfs 를 수행하고 최소 방문 순서를 업데이트 한다.
#02. 이미 방문했으나, 아직 그 어떤 scc 에 속하지 않은 경우, (무시해야 하는 교차 간선이 아님)
=> 최소 방문 순서를 업데이트 한다. - return 할 값이 이번에 방문 한 정점의 방문 순서와 같은 경우
=> u 를 루트로 하는 서브트리를 하나의 SCC 로 묶는다.
=> Stack 에서 저장 된 노드 번호를 u 까지 pop 한다.
=> scc id 를 업데이트(increment) 한다. - 최소 방문 순서를 반환한다.
타잔 알고리즘 구현은 DFS 와 Edge 유형과 관련이 있다.
[2. 문제 패턴, 적용 할 만한 상황]
- 입력으로 주어지는 그래프가 방향 그래프인 경우
- 입력으로 주어지는 그래프 내 Cycle 이 존재가 가능한 경우
- 모든 노드를 여러 번 방문 해도 되는 경우 => Cycle 과 연관이 있다.
- SCC 그래프가 필요 할 수도 있다.
=> SCC 그래프는 트리 형태라고 봐도 된다.
=> 모든 경로 를 탐색해볼 수 있다.
=> cost, weight 등이 같은 경우는 탐색에서 반드시 제외되어야 한다.
=> 탐색 범위 증가로 인해 메모리 초과 발생 가능성이 높다. - SAT 로 바꿔 풀 수 있는 경우
- ...
[3. 예제]
'알고리즘 > 분류' 카테고리의 다른 글
| 문자열-KMP 관련 솔루션 (0) | 2023.04.21 |
|---|---|
| 최소 공통 조상 솔루션 (0) | 2022.12.28 |
| 위상 정렬 솔루션 (0) | 2022.12.27 |
| 최소신장트리 솔루션 (0) | 2022.12.26 |
| 플로이드-워셜 솔루션 (0) | 2022.12.25 |
