[Python/백준] 20040. 사이클 게임

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

유니온파인드

https://www.acmicpc.net/problem/20040

---

풀이

import sys
input = sys.stdin.readline

# 0 ~ n-1 점 n개 주어짐
# 어느 세 점도 일직선 위에 놓이지 x.
# 매 차례 두 점 선택 긋는데, 교차는 가능.
# 사이클 완성 시 게임이 종료됨.
# 이전에 그은 선분만 다시 못 그을 뿐, 이미 뽑은 점 재선택은 가능
# 입력 : 점의 개수 n, 진행된 차례 수 m
# 출력 : m차례까지 게임 진행 후 사이클 만들어졌다면 만들어진 차례 번호 출력,
# 안만들어졌으면 0을 출력.
# 출력 단계는 1부터 시작해서 m까지임에 유의.

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    x_root = find(x)
    y_root = find(y)

    if x_root == y_root:
        # 이 두 점(x, y)를 이으면 사이클이 생기니,
        # 잇지 마!! 하는 의미로 False 반환
        return False

    if rank[x_root] > rank[y_root]:
        parent[y_root] = x_root
    elif rank[y_root] > rank[x_root]:
        parent[x_root] = y_root
    else:
        parent[y_root] = x_root
        rank[x_root] += 1

    return True

n, m = map(int, input().split())
parent = list(range(n))
rank = [0] * n

for stage in range(1, m + 1):
    x, y = map(int, input().split())

    if not union(x, y): # 사이클이 생기면 잇지 말라고 False 반환하게 만들자.
        print(stage)
        break

else:
    print(0)

---

강사님 풀이 들으며 필기

import sys
input = sys.stdin.readline

# 이 문제는 '사이클' 키워드가 등장했으니, 유니온 파인드를 떠올릴 수 있어야함.
# 사이클은 유니온 파인드의 대표 소재.

def find(x):
    if x != parent[x]:
        parent[x] = find(parent[x])
    return parent[x] # 사실상 x 반환해도 같음

def union(x, y):
    x_root = find(x)
    y_root = find(y)
    # 루트가지고 통합을 해야 두 집합이 통합이 되니까.
    # 중간 꺼 가지고 붙여버리면 끊겨버릴 수 있으니까.

    # 원래 코드에도 있던 부분이었지만, 여기서는 이게 사이클을 판별하는 로직으로도 작동함.
    # 일종의 백트래킹.
    if x_root == y_root:
        return False

    if rank[x_root] > rank[y_root]:
        parent[y_root] = x_root
    # 이렇게 랭크가 큰 노드한테 작은 노드를 붙여주는 이유:
    # 그렇게 붙여야 트리가 최대한 안정적인 구조를 유지해서
    # 높이가 최대한 작게 됨.
    elif rank[x_root] < rank[y_root]:
        parent[x_root] = y_root
    else:
        parent[x_root] = y_root
        rank[y_root] += 1

    return True

n, m = map(int, input().split())
parent = list(range(n))
rank = [0] * n

for t in range(1, m + 1):
    x, y = map(int, input().split())

    # union
    # union이 제대로 되었으면 -> 넘어감
    # union이 제대로 되지 않았으면 -> 사이클 발생 알리고 종료
    if not union(x, y):
        # union이 제대로 되면 True가 반환되어 나가도록 짤 거임.
        print(t)
        break

# 파이썬 if else indentation 테크닉
else:
    print(0)