SCC(Strongly Connected Component) 알고리즘
참조 ) 안경잡이개발자 : 네이버 블로그, Geeks for Geeks
‘강한 연결 요소’란?
- 방향성이 존재하는 유향 그래프에서, 그래프의 정점 그룹 X에서 어떤 두 정점 A,B 간의 경로가 항상 존재할 때, 그 집합을 ‘강하게 연결되었다’라고 표현한다. 이 강하게 연결된 집합을 ‘강한 연결 요소’라 정의한다.
- DFS를 기반으로하는 선형 탐색 알고리즘을 사용해 강한 연결 요소를 탐색할 수 있다.
- 강한 연결 요소를 추출하는 알고리즘에는 ‘
코사라주 알고리즘’과‘타잔 알고리즘’이 있다.
SCC의 필요 조건
- 같은 SCC내의 임의의 정점 A,B 사이 경로가 항상 존재한다.
- 서로 다른 SCC에서 뽑은 임의의 두 점 A,B 사이에서 A→B로 가는 경로와 B→A로 가는 경로는 동시에 존재할 수 없다. (SCC 끼리는 사이클이 존재하지 않는다.)
코사라주 알고리즘
- 주어지는 방향을 그대로 기록한 정방향 그래프와, 방향을 반대로 작성한 역방향 그래프 두 개가 필요하다. 즉, 코사라주 알고리즘에선
정방향 그래프,역방향 그래프,스택세 가지가 필요하다. - 정방향 그래프에서 DFS를 수행하며 탐색이 끝난 정점들을 순서대로 stack에 넣었다가, 역방향 그래프에서 해당 stack에서 원소를 하나 씩 꺼내며 DFS로 탐색한다.
- ‘DFS→ Stack으로 visited 조정 → DFS’ 순으로 알고리즘이 진행된다.
- 시간복잡도는 O(V+E)이다.
알고리즘 설명
- 주어진 방향 그래프의 역방향 그래프를 만들어 임의의 정점부터 DFS를 수행
- DFS가 끝나는 순서대로 스택에 삽입
- 아직 방문하지 않은 정점들에 대해 DFS를 수행
- 모든 정점이 스택에 담긴 후에는 스택을 pop하여 나오는 정점부터 역방향 그래프에서 DFS를 수행함. 이미 방문한 정점은 pop만 시행
- 탐색되는 모든 정점을 SCC로 추가한다.
- 스택이 빌때까지 진행한다.
타잔 알고리즘
- 모든 정점에 대해 DFS를 수행하여 SCC를 찾는 알고리즘으로, 단 한번만의 탐색으로 SCC를 찾는다.
- 하나의 정점을 방문할 때, 해당 정점의 간선을 탐색하며 방문한 정점의 부모와 연결된 정점 집합이 있다면 그 정점들로 구성된 SCC가 존재한다고 판단한다. → 즉, 방향 경로의 시작점으로 돌아갈 수 있어야 같은 SCC에 속한다.
- 같은 SCC에 속하는 노드들은 같은 부모를 갖는다.
- 시간복잡도는 코사라주 알고리즘과 같이 O(V+E)이다.
알고리즘 설명
- DFS시 탐색할 노드들 중에서 가장 낮은 번호를 부모로 지정한다.
- 인접 정점에 방문하여 자기 자신을 스택에 넣고, DFS를 수행
- 인접 정점에 방문할때, 아직 탐색을 처리중인 경우 ‘더 작은 값’을 부모로 갱신
- 부모의 DFS가 끝난 경우, 자신의 값이 스택에서 나올 때까지 스택의 노드들을 모두 pop하고 SCC배열에 추가한다.
- 만들어진 Sub SCC를 전체 SCC 배열에 추가한다.
SCC 알고리즘 문제 예시 - 백준 10265 MT
# 문제조건
- 각 사람이 원하는 '같이 갈 사람'이 주어졌을 때, 버스에 태울 수 있는 '최대 인원'을 구한다.
- 입력은 첫번째 줄에 사람 수 'n'과 태울 수 있는 사람 수 'k'가 주어진다.
- 두번째 줄에 n개의 정수가 차례대로 주어진다. 이 정수는 해당 정수 번호의 사람이 버스에 타지 않는다면, n번째 사람도 버스에 타지 않음을 의미한다.
- 단, 위 조건의 역은 성립하지 않는다. n번째 사람이 타지 않는다고, 정수번째 사람이 타지 않는건 아니다.아이디어
그래프는 단방향으로 주어진다. 주어진 서브 그래프들은 ‘SCC’이며, 각각의 SCC 크기를 배열에 넣고 그 중 최대 인원 k보다 작으면서 가장 큰 SCC 크기를 출력한다.
부모값과 현재 노드를 mapping한 리스트를 쓰거나 리스트 두 개로 탐색 상태를 트래킹하고, SCC를 이차원 배열 혹은 딕셔너리에 저장한다.
구현중인 코드
# 아직 수정 중!
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
n, k = map(int,input().split()) # n은 사람 수, k는 버스에 태울 수 있는 사람의 수이다.
# init tree(graph)
graph = {i : [] for i in range(1, n+1)} #index번째 노드의 연결 관계를 기록한다
r_graph = {i : [] for i in range(1, n+1)} #index번째 노드의 연결 관계를 기록한다 reversed_graph
visited = [False for _ in range(n+1)] # 탐색 여부를 기록하고, True이면 해당 노드의 탐색이 끝나 다시 방문하지 않는다
v = ['' for num in range(n)]
result = [[] for num in range(n)]
idx = []
st = []
SCC = []
global id
id = 0
def dfs(i):
global id
id += 1
idx[i] = id
st.append(i)
parent = idx[i]
for j in range(n+1):
k = v[i][j]
if idx[j] == 0:
parent = min(parent, dfs(k))
elif visited[j] == False:
parent = min(parent, idx(k))
if parent == idx[i]:
scc=[]
while 1:
tmp = st.top()
st.pop()
scc.append(tmp)
visited[tmp] = True
if tmp == i:
break
SCC.append(scc)
return parent
#간선 개수 만큼 그래프 작성
list = input().split()
idx = 1
for n in list:
graph[idx].append(int(n)) # 정방향 그래프
r_graph[int(n)].append(idx) # 역방향 그래프
v[idx-1] += n
idx += 1
print(graph)
print(r_graph)
print(v)
for i in range(int(n)):
if visited[i] == 0 :
dfs(i)
print(SCC)
멘티를 넘어 멘토가 되는 그날까지 파이팅