본문 바로가기
728x90
반응형

유니온파인드

Algorithm & Data Structure 2022. 8. 17. 백준 - 1976번(유니온 파인드, 재귀) https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net import sys sys.setrecursionlimit(200000) def find(a): if a == arr[a]: return a x = find(arr[a]) arr[a] = x return arr[a] def union(a,b): a = find(a) b = find(b) if a == b: return arr[max(a,b)] = arr[min(a,b)] n = int(sys.st..
Algorithm & Data Structure 2022. 8. 16. 백준 - 1717번(유니온 파인드, 재귀, 집합) https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 문제 자체가 이해가 어렵지는 않은 문제다. 이 문제를 풀기 위해서는 유니온 파인드가 뭔지 알아야 한다. 그래프 풀이법의 일종으로 볼 수 있다. 노드들을 합치고(union), 부모를 찾아준다(find) 일련의 과정은 다음과 같다. 1. 원소 두 개를 입력받고 Union 함수를 호출한다. 2. 입력받은 원소의 부모를 find 함수를 이용해서 '재귀적으로' 찾아..
728x90
반응형

티스토리툴바