강한 연결 요소
Tarjan 알고리즘으로 서로 도달 가능한 노드를 그룹화합니다
강한 연결 요소은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
SCC란
강연결 요소는 방향 간선을 따라 이동했을 때 모든 정점에서 다른 모든 정정점으로 도달할 수 있는 최대 정점 그룹입니다.
중요한 이유
각 SCC를 하나의 초정점으로 합치면 모든 방향 그래프를 DAG로 바꿀 수 있습니다. 그러면 서로 얽힌 의존성을 쉽게 분석할 수 있습니다.
한 번의 탐색으로 Tarjan 알고리즘 수행하기
Tarjan 알고리즘은 한 번의 DFS로 모든 SCC를 찾습니다. 실행 시간은 O(V + E)로, 일반적인 탐색 한 번과 같습니다.
발견 번호
DFS가 각 정점을 처음 방문한 순서대로 발견 시간을 부여합니다. 이 번호를 사용하면 어떤 정점을 먼저 방문했는지 비교할 수 있습니다.
disc = [-1] * n
timer = 0로우 링크 값
각 정점의 로우 링크는 역방향 간선을 통하는 경우까지 포함해 해당 정점에서 도달할 수 있는 가장 작은 발견 번호입니다. 이 값이 요소의 기준점이 됩니다.
low = [-1] * n스택에 넣기
DFS가 정점에 들어가면 disc와 low를 설정한 다음, 같은 요소에 속할 가능성이 있는 정점들의 스택에 넣습니다.
disc[u] = low[u] = timer
timer += 1
stack.append(u)
on_stack[u] = True자식에서 low 갱신하기
방문하지 않은 자식으로 재귀 호출한 뒤에는 자식의 low 값을 위로 가져옵니다. low[u]를 자기 자신과 자식의 low 중 최솟값으로 설정합니다.
dfs(v)
low[u] = min(low[u], low[v])역방향 간선 처리하기
인접 정점이 이미 스택에 있다면 현재 SCC의 조상입니다. 그 정점의 disc를 사용해 low[u]를 낮춥니다.
elif on_stack[v]:
low[u] = min(low[u], disc[v])요소의 루트 찾기
low[u]가 disc[u]와 같아지면 정점 u는 SCC의 루트입니다. 스택에서 u보다 위에 있는 모든 정점이 같은 요소에 속합니다.
요소 꺼내기
루트에서는 u가 제거될 때까지 스택에서 정점을 `pop`합니다. 이렇게 꺼낸 그룹이 정확히 하나의 강연결 요소입니다.
while True:
w = stack.pop()
on_stack[w] = False
comp.append(w)
if w == u: break대안으로 사용하는 Kosaraju 알고리즘
두 번의 탐색을 선호하시나요? Kosaraju 알고리즘은 DFS를 수행하고, 모든 간선의 방향을 뒤집은 다음, 종료 순서에 따라 다시 DFS를 수행해 SCC를 분리합니다.
빠른 확인
Tarjan의 DFS 중 정점 u가 low[u] == disc[u]를 만족합니다. 이것은 무엇을 의미합니까?
복습: Tarjan으로 SCC 찾기
한 번의 DFS에서 disc와 low를 추적하고, 현재 탐색 중인 정점을 스택에 저장하며, low가 disc와 같아질 때마다 요소를 `pop`합니다. O(V+E)에 SCC를 찾을 수 있습니다. 🧩
자주 묻는 질문
“강한 연결 요소” 강의는 무료인가요?
네 — “강한 연결 요소” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“강한 연결 요소”에서 뭘 배우나요?
Tarjan 알고리즘으로 서로 도달 가능한 노드를 그룹화합니다 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“강한 연결 요소” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.