[이것이 코딩 테스트다] 사이클 발생 확인 with Python

🔒 문제

서로소 집합 알고리즘을 응용하면 사이클 생성 여부를 판단할 수 있다.
그래프 사이에 사이클이 발생했는지 확인하는 알고리즘을 작성하시오.

입력

3 3
1 2
1 3
2 3

출력

사이클이 발생했습니다.

✅ 해설

• 사이클 발생 여부를 서로소 집합 알고리즘으로 어떻게 알 수 있을까?
  • 예를 들어, 노드1과 노드2, 노드3이 존재한다.
  • 노드1과 노드2가 연결돼 있다면 부모 테이블은 table = [0, 1, 1, 3] 이고,
  • 노드1과 노드3이 연결돼 있다면 부모 테이블은 table = [0, 1, 1, 1]이다.
  • 마지막으로 노드2와 노드3이 연결돼 있다면 table[2] 와 table[3]은 1로 그 값이 같아진다.
  • 이와 같이 연결된 두 노드가 주어질 때, 두 노드의 최상위 부모 노드 값이 같다면, 이는 사이클이 생김을 의미한다.

💻 코드

# 노드의 개수와 간선의 개수 입력받기
v, e = map(int, input().split())

# 부모 테이블을 자기 자신 노드로 초기화
table = []
for i in range(v+1):
    table.append(i)

# 최상위 부모 노드를 찾아서 반환
def get_top_node(node):
    # 특정 노드의 부모 노드를 가져옴
    parent = table[node]
    # 만약 최상위 노드가 아니라면
    if parent != table[parent]:
        parent = get_top_node(parent)
    return parent

# 싸이클 판별 함수
def union(n1, n2):
    # 각 노드의 부모 노드를 찾기
    parent1 = get_top_node(n1)
    parent2 = get_top_node(n2)

    # 사이클 판별
    if parent1 == parent2:
        print("사이클이 발생했습니다.")
        return
    # 각 노드의 부모 노드 중 더 작은 값을 최상위 부모 노드로 설정
    elif parent1 < parent2:
        # 부모 노드 테이블 업데이트
        table[n2] = parent1
    else:
        table[n1] = parent2

# 간선 정보 입력받기
for i in range(e):
    n1, n2 = map(int, input().split())
    union(n1, n2)