브리지와 단절점
연결을 끊는 간선과 노드를 찾습니다
브리지와 단절점은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
그래프의 취약한 지점
무방향 그래프의 일부는 핵심적입니다. 이를 제거하면 그래프가 분리되기 때문입니다. 이런 지점을 찾으면 취약한 연결을 알아낼 수 있습니다.
브리지란
브리지는 제거했을 때 연결 요소의 수를 증가시키는 간선입니다. 두 영역을 잇는 유일한 경로이기도 합니다.
단절점이란
단절점은 제거하면 그래프를 분리시키는 정점입니다. 네트워크에서는 이런 단일 장애 지점을 특히 주의해야 합니다.
다시 보는 DFS 트리
두 방법 모두 한 번의 DFS를 수행하면서 발견 시간과 low 값을 추적합니다. Tarjan 알고리즘과 비슷하지만 무방향 그래프에 적용합니다.
disc = [-1] * n
low = [-1] * nlow는 가장 이른 도달을 뜻함
정점의 low는 DFS 하위 트리에서 도달할 수 있는 가장 이른 발견 번호이며, 위쪽으로 역방향 간선을 하나 거칠 수도 있습니다.
진입 시 초기화하기
DFS가 정점에 들어가면 현재 타이머 값으로 disc와 low를 기록하고 인접 정점으로 계속 진행합니다.
disc[u] = low[u] = timer
timer += 1브리지 조건
자식 v로 재귀 호출한 뒤 low[v] > disc[u]라면 u를 건너뛰는 역방향 간선이 없다는 뜻이므로 간선 u-v는 브리지입니다.
if low[v] > disc[u]:
bridges.append((u, v))단절점 조건
루트가 아닌 u는 자식 v가 low[v] >= disc[u]를 만족할 때 단절점입니다. v의 하위 트리가 u를 우회할 수 없기 때문입니다.
if parent[u] != -1 and low[v] >= disc[u]:
art.add(u)루트의 특수한 경우
DFS 루트는 DFS 트리에서 자식이 두 명 이상일 때만 단절점이 되므로, 자식 수를 세어야 합니다.
if parent[u] == -1 and children > 1:
art.add(u)부모 간선 건너뛰기
역방향 간선으로 low를 갱신할 때는 부모로 이어지는 간선을 따라 되돌아가면 안 됩니다. 그렇지 않으면 브리지를 잘못 판별하게 됩니다.
if v != parent[u]:
low[u] = min(low[u], disc[v])한 번의 탐색으로 두 결과 얻기
한 번의 DFS로 모든 브리지와 단절점을 함께 찾아낼 수 있으며, 실행 시간은 O(V + E)입니다. 추가 탐색은 필요하지 않습니다.
빠른 확인
u에서 자식 v로 재귀 호출한 뒤 low[v] > disc[u]임을 확인했습니다. 무엇을 찾은 것입니까?
복습: 핵심 간선과 정점
disc와 low를 사용하는 한 번의 DFS로 모든 것을 찾을 수 있습니다. low[v] > disc[u]이면 브리지이고, low[v] >= disc[u]이면 단절점입니다. 🌉
자주 묻는 질문
“브리지와 단절점” 강의는 무료인가요?
네 — “브리지와 단절점” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“브리지와 단절점”에서 뭘 배우나요?
연결을 끊는 간선과 노드를 찾습니다 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.
“브리지와 단절점” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.