devbelly

문제 https://www.acmicpc.net/problem/3108 알고리즘 Union-Find 풀이 좌표평면 위 사각형들이 주어졌을 때, (0,0)에서 시작하여 PU명령을 몇 번 해야 하는지 묻고 있습니다. 거북이는 (0,0)에 펜을 내리고 있는 상황입니다. 문제에서 주어진 예제를 그려본다면 (5,0) 과 (8,3)으로 이루어진 사각형을 제외하고는 모든 사각형이 이어져있음을 알 수 있습니다. PU명령이 필요할 때는 이어져 있지 않은 사각형을 그리러 갈 때입니다. 즉 사각형들이 이어져 있다면 하나의 그룹으로 카운트를 할 수 있는 유니온파인드를 사용합시다. 이중 포문을 통해 모든 사각형들이 겹치는지 안겹치는지를 확인하는 과정에서 겹친다면 유니온을 진행합니다. 유니온의 기준은 인덱스 번호가 큰 쪽으로 유..