본문 바로가기

알고리즘

그래프 사이클 감지

Basic 100 · 50번Lv. 3그래프 탐색(BFS·DFS)

그래프 사이클 감지

문제 설명

주어진 방향 그래프에서 사이클이 존재하는지 확인하는 함수를 작성해주세요. 그래프는 딕셔너리 형태로 표현되며, 키는 노드를 나타내고 값은 해당 노드에서 직접 이동할 수 있는 이웃 노드들의 리스트입니다.

예를 들어, 그래프가 {"0": ["1"], "1": ["2"], "2": ["0", "3"], "3": ["4"], "4": ["5"], "5": []}로 주어진다면, 사이클이 존재합니다 (0 -> 1 -> 2 -> 0).


제한 사항

  • 노드의 수는 1 이상 100 이하입니다.
  • 각 노드는 0부터 시작하는 정수를 문자열로 쓴 이름("0", "1", …)으로 표현됩니다.
  • 입력 data는 {"graph": 그래프} 형태로 주어집니다(입출력 예는 그래프 부분만 적었습니다).

입출력 예

입력 (방향 그래프)반환값 (사이클 존재 여부)
{"0": ["1"], "1": ["2"], "2": ["0", "3"], "3": ["4"], "4": ["5"], "5": []}True
{"0": ["1"], "1": ["2"], "2": ["3"], "3": ["4"], "4": ["5"], "5": []}False
{"0": ["1", "2"], "1": ["3"], "2": [], "3": ["2"]}False

입출력 설명

주어진 방향 그래프에서 사이클이 존재하는지 여부를 True 또는 False로 반환합니다.

예시 테스트

#입력기대값
1{"graph": {"0": ["1"], "1": ["2"], "2": ["0", "3"], "3": ["4"], "4": ["5"], "5": []}}true
2{"graph": {"0": ["1"], "1": ["2"], "2": ["3"], "3": ["4"], "4": ["5"], "5": []}}false
3{"graph": {"0": ["1", "2"], "1": ["3"], "2": [], "3": ["2"]}}false

입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 8개도 함께 채점해요.