[Hackerrank] Cycle Detection

사이클 감지 (Cycle Detection)

문제 설명
연결 리스트가 순회 중에 동일한 노드를 두 번 이상 방문하면 해당 연결 리스트는 사이클이 포함되어 있다고 합니다. 연결 리스트의 헤드(head)가 주어졌을 때, 사이클이 포함되어 있는지 확인하세요. 만약 사이클이 있다면 1을 반환하고, 없으면 0을 반환하세요.

---

입력 형식

• 연결 리스트의 헤드(head)가 함수의 매개변수로 주어집니다.
• 연결 리스트의 노드들은 아래와 같은 구조를 가집니다:
  • int data: 노드의 값
  • SinglyLinkedListNode next: 다음 노드를 가리키는 포인터

---

출력 형식

• 연결 리스트에 사이클이 있다면 1을 반환합니다.
• 연결 리스트에 사이클이 없다면 0을 반환합니다.

---

제약 조건

• 연결 리스트의 크기: 0≤list size≤10000 

---

예제
입력 1
헤드가 다음 노드를 가리킴: 1 → 2 → 3 → NULL
출력 1
0
(사이클이 없음)

입력 2
헤드가 다음 노드를 가리킴: 1 → 2 → 3 → 1 (사이클 존재)
출력 2
1
(사이클이 있음)

자료구조 문제로 연결 리스트에 순환되는 부분이 있는지 없는지 확인하는 문제이다. 이를 해결하기 위해 다음과 같은 방법을 이용했다.

1. visit_list에 지나간 주소를 저장한다.

2. 리스트를 순회하며 현재 노드가 visit_list에 이미 존재한다면 순환이 존재한다는 뜻이므로 1을 반환

3. 현재 노드가 visit_list에 없다면 현재 노드의 주소를 visit_list에 추가

4. 순회를 완료했는데 사이클이 없다면 0을 반환

코드는 다음과 같다.

def has_cycle(head):
    visit_list = set()
    while head:
        if head in visit_list:
            return 1
        else:
            visit_list.add(head)
            head = head.next
            continue
    return 0

위 코드로 문제를 통과했지만, 구글링을 해보니 floyd's cycle detection algorithm이 있다는 것을 알게 되었다. 이 알고리즘은 2개의 포인터( 느린 포인터와 빠른 포인터)를 이용해서 만약 순환이 존재한다면 2개의 포인터가 만나는 지점이 있다는 부분을 활용해서 작성한 알고리즘이다.

def has_cycle(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next  # 한 칸 이동
        fast = fast.next.next  # 두 칸 이동

        if slow == fast:  # 두 포인터가 만난다면 사이클 존재
            return 1

    return 0  # 사이클 없음

위 코드를 보면 느린 포인터(slow)는 한 번에 한 노드씩 이동하고, 빠른 포인터(fast)는 한 번에 두 노드씩 이동한다. 만약 리스트에 사이클이 있다면, 두 포인터는 결국 만나게 된다. 이 방식을 통해 추가 메모리 사용 없이 사이클을 감지할 수 있다.
처음에 작성한 visit_list를 사용한 방식도 충분히 문제를 해결할 수 있었지만, Floyd’s Algorithm은 더 효율적이고 깔끔한 방법으로 문제를 해결할 수 있다는 점에서 유용하다는 것을 배울 수 있었다.