백준 10431 [알고리즘] 백준 1043 거짓말 백준 1043 거짓말문제의 키포인트는 진실을 아는 사람들의 리스트를 계속 갱신을 해줘야 하는데 그것을 어떻게 하느냐이다. 이러한 알고리즘에 최적인 유니온 파인드를 쓸 수 있다.유니온 파인드 알고리즘이란? 그래프 알고리즘의 일종으로서 상호 배타적 집합이라고 한다. 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘이다.import sysfrom collections import dequeimport heapqdef find(a): if a == parents[a]: return a return find(parents[a])def union(x,y): x = find(x); y = find(y) if x 1:.. 2024. 10. 16. 이전 1 다음