<aside> 💬 lv2, 데이터 구조, 깊이 우선 탐색(DFS)

그래프 사이클 감지

문제 설명

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

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

제한 사항

• 노드의 수는 1 이상 100 이하입니다.
• 각 노드는 0부터 시작하는 정수로 표현됩니다.

입출력 예

입출력 설명

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

</aside>

😺 풀이 1. DFS 알고리즘 이용1

def solution(data):
    def has_cycle(graph): #1 has_cycle 함수
        visited = set()
        rec_stack = set()

        for node in graph: #2 그래프의 모든 노드 반복
            if node not in visited: #3 현재 노드를 아직 방문하지 않았다면
                if dfs(graph, node, visited, rec_stack): #4 사이클이 발견되면
                    return True
        return False

    def dfs(graph, current, visited, rec_stack): 
        if current not in visited: #5 현재 노드가 방문 되지 않았다면
            visited.add(current)
            rec_stack.add(current)

            for neighbor in graph.get(current, []): #6 현재 노드의 모든 이웃에 대해 반복
                if neighbor not in visited:
                    if dfs(graph, neighbor, visited, rec_stack):
                        return True
                elif neighbor in rec_stack:
                    return True

        rec_stack.remove(current) ****#7 재귀 스택 제거
        return False

    return has_cycle(data["graph"])

단계별 풀이 전략

1. has_cycle 함수

   사이클이 존재하는지 확인하는 내부 함수를 호출하고, 그 결과를 반환합니다. visited = set() → 방문한 노드를 기록합니다. 중복 방문을 방지합니다.

   rec_stack = set() → 현재 DFS 탐색 경로에 있는 노드를 기록합니다. 사이클 탐지에 사용됩니다.

2. 그래프의 모든 노드에 대해 반복

   for node in graph → 그래프의 모든 노드에 대해 반복합니다.

3. 현재 노드를 아직 방문하지 않았다면

   현재 노드가 아직 방문 되지 않았다면, DFS 탐색을 시작합니다.

4. 사이클이 발견되면

   DFS 탐색을 통해 사이클이 발견되면 True를 반환하고, 사이클이 발견되지 않으면 False를 반환합니다.

5. 현재 노드가 방문 되지 않았다면

   현재 노드가 방문 되지 않았다면 현재 노드를 방문한 것으로 기록합니다.

   rec_stack.add(current) → 현재 노드를 재귀 스택에 추가합니다.

   사이클 탐지는 rec_stack을 사용하여 수행됩니다. rec_stack은 현재 DFS 경로에 있는 노드를 추적합니다. 만약 현재 노드에서 시작된 탐색 중에 rec_stack에 이미 있는 노드로 돌아온다면, 그래프에 사이클이 존재한다는 것을 의미합니다.

6. 현재 노드의 모든 이웃에 대해 반복

   현재 노드의 모든 이웃에 대해 반복합니다. 이웃 노드가 방문 되지 않았다면, 재귀 적으로 DFS 탐색을 계속합니다. 이웃 노드 탐색에서 사이클이 발견되면 True를 반환합니다. 이웃 노드가 현재 DFS 탐색 경로에 있으면, 사이클이 존재한다는 의미이므로 True를 반환합니다.

7. 재귀 스택 제거

   현재 노드 탐색을 마치면, 재귀 스택에서 제거합니다. 이는 다른 경로의 탐색에서 현재 노드가 재 방문 되는 것을 허용하기 위함입니다. 현재 경로에서 사이클이 발견되지 않으면 False를 반환합니다.

이 과정을 아래 data를 예를 들어 설명해 보겠습니다.

{"0": ["1"], "1": ["2"], "2": ["0", "3"], "3": ["4"], "4": ["5"], "5": []}

• 노드 "0" 처리
  • visited에 "0"을 추가합니다. visited = {"0"}.
  • rec_stack에 "0"을 추가합니다. rec_stack = {"0"}.
  • "0"의 이웃인 "1"로 DFS를 재귀 호출합니다.
• 노드 "1" 처리
  • visited에 "1"을 추가합니다. visited = {"0", "1"}.
  • rec_stack에 "1"을 추가합니다. rec_stack = {"0", "1"}.
  • "1"의 이웃인 "2"로 DFS를 재귀 호출합니다.
• 노드 "2" 처리
  • visited에 "2"를 추가합니다. visited = {"0", "1", "2"}.
  • rec_stack에 "2"를 추가합니다. rec_stack = {"0", "1", "2"}.
  • "2"의 이웃인 "0"과 "3"에 대해 DFS를 재귀 호출합니다.
• 노드 "2"에서 "0"으로의 재귀 호출 시도
  • "0"은 이미 visited에 있으며 rec_stack에도 존재합니다. 이는 "2"에서 "0"으로 가는 경로가 현재 DFS 경로에 있음을 의미하며, 사이클이 존재한다는 것을 나타냅니다. 따라서, 함수는 True를 반환하고 탐색을 종료합니다.

알아 둬야 할 개념

**깊이 우선 탐색(DFS, Depth-First Search)**은 그래프나 트리 구조에서 노드를 탐색하는 알고리즘 중 하나 입니다. DFS는 시작 노드에서 시작하여 한 방향으로 갈 수 있는 만큼 깊이 탐색을 진행하고, 더 이상 갈 수 없을 때 이전 노드로 돌아와 다른 방향으로 탐색을 진행하는 방식입니다.