출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 41, p 393 서로소 집합을 이용해 여행 계획 안에 있는 여행지들이 모두 같은 집합에 속하면 예행 계획이 가능한 것으로, 그렇지 않으면 불가능한 것으로 풀이했습니다. 연결된 도시들의 정보가 리스트가 아닌 행렬로 주어지므로 행렬의 값 중 0이 아니라 1인 부분의 좌표를 통해 연결된 도시들의 정보를 담은 리스트 links를 생성했습니다. 이를 이용해 서로소 집합 알고리즘을 수행하고, 계획에 있는 도시들이 속한 집합을 확인해 이들이 모두 같으면 YES, 아니면 NO를 출력했습니다. import sys # 입력 받아오기 inputs = list(map(int, sys.stdin.read().split())) # 여행지의 수 N = inputs[0..

1. 개선된 서로소 집합 알고리즘 - 서로소 집합Disjoint Sets: 공통 원소가 없는 두 집합 - 서로소 집합 자료 구조 = union-find 자료구조 (1) 개선된 서로소 집합 알고리즘 # 특정 원소가 속한 집합을 찾기 def find_parent(parent, x): # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출 if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] # 두 원소가 속한 집합을 합치기 def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a < b: parent[b]..