유향 그래프에서 사이클 감지하기
노드에 색을 칠해 역방향 간선을 찾습니다
유향 그래프에서 사이클 감지하기은(는) CoddyKit의 무료 Competitive Programming Academy 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Competitive Programming Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
사이클이 중요한 이유
방향 사이클은 의존성이 자기 자신에게 되돌아온다는 뜻입니다. 사이클을 찾으면 위상 순서나 유효한 일정이 존재할 수 없다는 것을 알 수 있습니다.
무방향 그래프는 다릅니다
여기서 사이클 감지는 방향과 관련이 있습니다. 간선을 잘못된 방향으로 따라가는 것은 세지 않으므로 무방향 그래프에서 쓰는 방법을 그대로 적용할 수 없습니다.
세 가지 색의 개념
각 정점에 세 가지 색 중 하나를 지정합니다. 흰색은 방문하지 않음을, 회색은 처리 중임을, 검은색은 완전히 처리했음을 뜻합니다.
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * n회색은 스택에 있다는 뜻
회색 정점은 현재 DFS 경로 위에 있습니다. 해당 정점에는 들어갔지만 아직 모든 자손을 탐색하지는 않은 상태입니다.
정점에 들어가기
DFS가 정점에 도달하면 탐색하기 전에 정점을 회색으로 칠합니다. 그러면 해당 정점이 현재 활성 경로의 일부임을 표시할 수 있습니다.
def dfs(u):
color[u] = GRAY역방향 간선 신호
이미 회색인 인접 정점에 도달했다면 현재 경로로 들어오는 역방향 간선을 찾은 것입니다. 이것은 사이클입니다.
for v in adj[u]:
if color[v] == GRAY:
return True # cycle흰색 정점으로 재귀하기
흰색 인접 정점은 아직 탐색하지 않은 정점이므로 그 정점으로 재귀 호출합니다. 더 깊은 호출에서 사이클을 보고하는 순간 참을 상위 호출로 전달합니다.
elif color[v] == WHITE and dfs(v):
return True검은색은 안전함을 뜻함
검은색 인접 정점은 탐색을 완료했고 사이클도 없으므로 무시해도 됩니다. 다시 방문하면 시간만 낭비하게 됩니다.
정점 처리 완료하기
모든 인접 정점을 처리한 뒤 해당 정점을 검은색으로 칠합니다. 그러면 현재 활성 경로에서 빠지고 처리가 완료된 것으로 표시됩니다.
color[u] = BLACK
return False모든 연결 요소 확인하기
그래프는 연결되지 않았을 수 있으므로, 아직 흰색인 모든 정점에서 DFS를 시작해야 그래프 전체를 빠짐없이 확인할 수 있습니다.
if any(color[u]==WHITE and dfs(u) for u in range(n)):
print('cycle')재귀 한도에 주의하기
깊은 그래프에서는 Python의 재귀 스택이 넘칠 수 있습니다. 한도를 높이거나 명시적인 스택을 사용하는 DFS로 다시 작성하십시오.
import sys
sys.setrecursionlimit(300000)빠른 확인
DFS 중 현재 회색인 인접 정점에 도달했습니다. 방금 무엇을 찾았습니까?
복습: 사이클 감지
정점을 흰색, 회색, 검은색 순서로 칠합니다. DFS 중 회색 인접 정점을 만나면 역방향 간선이므로 방향 사이클이 있다는 증거입니다. 🔁
자주 묻는 질문
“유향 그래프에서 사이클 감지하기” 강의는 무료인가요?
네 — “유향 그래프에서 사이클 감지하기” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Competitive Programming Academy 강의 전체를 잠금 해제할 수 있습니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“유향 그래프에서 사이클 감지하기”에서 뭘 배우나요?
노드에 색을 칠해 역방향 간선을 찾습니다 브라우저에서 직접 실행하는 실습 코드로 Competitive Programming Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Competitive Programming Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Competitive Programming Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“유향 그래프에서 사이클 감지하기” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Competitive Programming Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Competitive Programming Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 칸의 알고리즘으로 위상 정렬
- 유향 그래프에서 사이클 감지하기
- 강한 연결 요소
- 브리지와 단절점