문제 www.acmicpc.net/problem/17619 17619번: 개구리 점프 첫 번째 줄에 통나무 개수 N과 질문의 개수 Q가 주어진다. 다음 N개의 줄에 각 통나무에 x1, x2, y의 세 정수 좌표가 주어진다. 주어진 통나무는 두 점 (x1, y)와 (x2, y)를 잇는 형태이다. (x1 < x2) 모든 www.acmicpc.net 풀이 solved.ac 난이도: Gold 3 정렬과 분리 집합(Disjoint set)으로 해결하는 문제이다. 이번 문제의 분리 집합의 구현에 사용하는 Union-Find(유니온-파인드) 자료구조에 대해서는 아래 게시글에 정리해두었다. 유니온-파인드(Union-Find), 분리 집합 이번 문제에서는 점프로 이동 가능한 통나무들을 한 집합으로 묶어 서로 이동 가능한..

문제 https://www.acmicpc.net/problem/1761 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 트리에는 두 노드의 경로는 유일하다. 두 노드의 쌍을 받은 후 한 노드에서 다른 노드로 직접 이동하며 거리합을 구하는 것이 가장 간단한 해결 방법이겠지만, 어느 경로로 이동해야 다른 노드로 이동할 수 있는지 알 수 없다. 따라서 최소 공통 조상(LCA)을 구하여 각 노드에서의 LCA로의 거리의 합을 구하면 두 노드 사이의 거리를 알 ..