union-find 썸네일형 리스트형 10. 유니온 파인드 (Union-Find) 유니온 파인드는 앞에서 공부한 최단 경로 탐색 알고리즘과 맥락을 달리하는 그래프 문제입니다. 최단 경로 탐색 알고리즘은 여러 노드와 간선 정보가 주어졌을 때 특정 노드에서 다른 노드로 이동하는데 얼마나 적은 비용으로 이동할 수 있는지 비용을 최소화 시키는 것을 목적으로 한다면 유니온 파인드 알고리즘은 노드간 연결 관계를 파악하고 특정 간선을 연결할 시 노드 연결관계가 어떻게 변화하는지 파악하는 알고리즘입니다. 예를 들어 설명하도록 하겠습니다. 어느 나라에 여러 도시들이 있었는데 도로가 하나도 안깔려있어서 서로 단절되어 있었습니다. 도시를 연결해야겠다고 생각한 한 사람이 도시 사이에 도로를 놓기로 했습니다. 하지만 어떤 도시들 사이에는 산이 있어서 직접 도로를 못 놓는 경우도 있었기 때문에 연결이 가능한 .. 이전 1 다음