문제 https://www.acmicpc.net/problem/2162 2162번: 선분 그룹 첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하 www.acmicpc.net 해결 방법 이 문제를 풀기 위해 두가지 알고리즘을 알아야 함 CCW를 사용해 두 선분이 겹치는지 판단 Union-Find를 통해 그룹을 합치고 확인하는 작업 진행 위 두 알고리즘을 알고 같이 사용한다면 쉽게 해결할 수 있음 입력받은 모든 선분들끼리 서로 겹치는지 판단 선분이 겹치는지는 CCW를 통해 판단 두 선분이 겹친다면 Union 과정 진행 위 작업이 끝..

Union-Find 설명 및 백준 1717번 문제 풀이 https://chb2005.tistory.com/81 [JAVA] Union-Find Union-Find 란? Union : 특정 2개의 노드를 연결해 1개의 집합으로 묶는 작업 Find : 특정 2개의 노드가 같은 집합에 속해 있는지 확인하는 작업 다음과 같이 6개의 노드가 있다고 가정 (1, 2), (2, 3), (4, 6), chb2005.tistory.com

Union-Find 란? Union : 특정 2개의 노드를 연결해 1개의 집합으로 묶는 작업 Find : 특정 2개의 노드가 같은 집합에 속해 있는지 확인하는 작업 다음과 같이 6개의 노드가 있다고 가정 (1, 2), (2, 3), (4, 6), (3, 6) 을 연결했을 때, 생기는 그룹은 몇개일까? group[1~6] = [1, 2, 3, 4, 5, 6]으로 초기화 이는 각 index가 속한 그룹의 대표값이라 생각하면 됨 1, 2 연결 노드 1과 노드 2의 대표값이 다름 => group[2]에 1을 넣어줌 => group = [1, 1, 3, 4, 5, 6] 2, 3 연결 노드2와 노드 3의 대표값이 다름 => group[3]에 노드2의 대표값 1을 넣어줌 => group = [1, 1, 1, 4, 5..