[백준] 20040 사이클 게임

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

노드들 간에 사이클로 연결이 되어있는지 판단을 하기 위하여 서로소를 이용하였습니다.

서로소는 두개의 노드가 연결이 되어 있다면 하나의 동일한 최상위 부모를 가리키게 됩니다.

 

따라서 두 노드의 최상위 노드가 서로 다르면 연결이 되어 있지 않으므로 연결을 시켜주고, 두 노드의 최상위 노드가 같으면 이미 연결이 되어 있으므로 현재 간선을 잇게 된다면 사이클이 형성되는 방식을 이용하였습니다.

2) 알고리즘

• 서로소 알고리즘

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

def find(x):                                            # 최상위 부모 노드 탐색
    if x != s[x]:                                       # 현재 노드가 최상위가 아니면
        x = find(s[x])                                  # 최상위 부모 탐색
    return x

def union_set(x, y):                                    # 두개의 노드를 서로 합침
    x = find(x)                                         # x의 최상위 부모를 찾음
    y = find(y)                                         # y의 최상위 부모를 찾음

    if x != y:                                          # 서로 최상위 부모가 다르면
        s[y] = find(x)                                  # 하나로 합침
        return False
    else:                                               # 최상위 부모가 같다면 사이클 형성
        return True

N, M = map(int, sys.stdin.readline().split())           # 노드의 개수, 간선의 개수
s = list(range(N))                                      # 서로소 집합 구분을 위한 리스트

for i in range(1, M+1):
    a, b = map(int, sys.stdin.readline().split())       # 두개의 노드
    
    if a > b:                                           # a와 b 중 a가 큰값이 되도록 설정
        a, b = b, a

    if union_set(a, b):                                 # a와 b를 합침
        print(i)                                        # 사이클 발견되면 종료
        break
else:                                                   # 사이클이 없는 경우
    print(0)

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

특별히 없습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

20040번: 사이클 게임

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다