[서로소 집합] 여행 계획

[ericagong]

⭐ 성찰

1. 집합 자료형을 이용하여 모두 같은 root 노드를 갖는지 판단 가능
2. 여행 계획 가능한지 그래프를 직접 그려보며, 어떠한 조건이 여행 계획 가능과 동치인지 파악해야함

❓ 문제 상황

[여행 계획](이코테 p. 393)

👨‍💻 문제 해결: 서로소 집합 알고리즘

✅ 1차 풀이: 여행 계획 가능 = 계획 내 모든 노드가 같은 root 노드 가지는지 판단

1. n * n 행렬 그래프에서 연결된 노드인 경우, union 연산을 수행
2. plan에 포함된 모든 노드가 같은 root 노드 가지는지 find 연산 수행 결과를 set에 집어 넣어 set 길이로 판단

   
   import sys

input = sys.stdin.readline

n, m = map(int, input().split()) graph = [[] for _ in range(n + 1)] p = [0] * (n + 1) for i in range(1, n + 1): p[i] = i

def find_parent(p, x): if x != p[x]: p[x] = find_parent(p, p[x]) return p[x]

def union_parent(p, a, b): a = find_parent(p, a) b = find_parent(p, b) if a < b: p[b] = a else: p[a] = b

여행 계획에 속한 모든 루트 노드가 동일한지 판단

def check_plan(plan): parents = set() for item in plan: parents.add(find_parent(p, item))

print('YES' if len(parents) == 1 else 'NO')

for i in range(n): data = list(map(int, input().split())) for j in range(n):

연결된 경우, union 연산 수행

    if data[j] == 1 and i > j:
        union_parent(p, i, j)

plan = list(map(int, input().split())) check_plan(plan)

[ericagong]

👍 리뷰 완료