https://www.acmicpc.net/problem/1774 🌌 자바로 푸는 우주신과의 교감 문제 풀이 📌 문제 개요 백준 1774번 우주신과의 교감 문제는N개의 신들과 이미 연결된 M개의 통로 정보가 주어졌을 때,모든 우주신이 연결되도록 추가로 연결해야 할 최소 거리의 합을 구하는 문제입니다. 각 우주신은 2차원 좌표 위에 존재이미 연결된 통로는 추가 비용 없이 사용 가능목표는 전체 우주신을 연결하는 최소 비용 💡 예제 입력4 11 12 22 43 31 4 예제 출력2.00 🛠 알고리즘 접근 방식 이 문제는 기존 연결 정보를 고려한 최소 신장 트리(MST) 문제입니다. ✅ 핵심 아이디어 크루스칼 알고리즘을 사용해 거리 기준 오름차순 간선 선택M개의 이미 연결된 통로는 먼저 uni..

🔁 자바로 푸는 사이클 게임 문제 풀이 📌 문제 개요 백준 20040 - 사이클 게임 문제는N개의 정점이 있고, M개의 간선을 순차적으로 연결할 때사이클이 처음 생기는 시점을 출력하는 문제입니다. 간선은 차례로 연결되며,간선을 연결할 때 사이클이 생기면 그 **차례(1-indexed)**를 출력끝까지 사이클이 없으면 0을 출력 💡 예제 입력6 50 11 22 30 34 5 예제 출력4 🧠 알고리즘 접근 방식 이 문제는 전형적인 Union-Find(서로소 집합) 알고리즘을 활용해사이클을 탐지하는 문제입니다. 간선을 하나씩 연결하며, 두 노드가 이미 같은 집합이면 사이클 발생그렇지 않으면 두 집합을 합침 (union)사이클이 생긴 첫 번째 간선의 번호를 출력 🧾 코드 해설// 부모 배열 초기..

https://www.acmicpc.net/problem/2162    선분 교차 여부를 판별해 선분 그룹을 나누고,각 그룹의 크기와 전체 그룹의 개수를 계산하여 풀이했다.입력으로 주어진 선분들을 Line 객체로 저장하고,Union-Find 자료구조를 사용해 선분 교차 관계를 기반으로 그룹을 형성한다.각 선분은 시작점과 끝점을 Dot 객체로 표현하며,시작점이 항상 더 작은 값을 가지도록 정렬하여 일관성을 유지한다. 두 선분의 교차 여부는 isCross 메서드를 통해 확인하며,CCW 메서드를 사용해 세 점이 반시계 방향,시계 방향, 또는 일직선상에 있는지를 판별한다.교차하는 경우 Union-Find의 union 메서드를 통해 두 선분을 같은 그룹으로 합친다.그룹은 size 배열을 통해 크기를 관리하며,경로..

https://www.acmicpc.net/problem/1647   이 문제는 크루스칼 알고리즘을 사용해 최소 스패닝 트리(MST)를 구하면서가장 큰 간선 비용을 제외해 두 개의 연결된 부분으로 나누는 문제다.목표는 모든 정점을 최소 비용으로 연결하는 트리를 구성하되,가장 큰 비용의 도로를 제외해 두 개의 분리된 부분으로 만드는 것이다. 먼저 main 메서드에서 정점 개수 N과 간선 개수 M을 입력받고,유니온-파인드를 위한 부모 배열 p를 초기화한다.각 간선의 정보를 입력받아 우선순위 큐 pq에 저장하며,큐는 간선의 비용을 기준으로 오름차순 정렬된다. calculate 메서드는 크루스칼 알고리즘을 사용해 MST를 구한다.우선순위 큐에서 가장 작은 간선부터 하나씩 꺼내어,두 정점이 이미 연결되어 있지 않..

https://www.acmicpc.net/problem/1197   크루스칼 알고리즘을 활용하여 문제를 풀이하였다.최근 문제 풀이한 것 중에서 크루스칼이 있었고 간선을 가중치기준으로 정렬하여풀었던 기억이 있어 그방식대로 풀었다. 풀이과정은 비교적 간단하고이번 문제 풀이에서 기억에 남는것은  union find 를 활용할 때경로 압축이다. find() 함수에서 if(p[a] == a) 일때 return a를 하는것이아니라if(p[a]!=a) 일때 p[a] = find(a)를 해주고 return p[a] 를 하게되면 정점의갯수가 많아지고 간선이 많아지더라도 시간복잡도가 확실히 줄어든 다는점을알게되었다. 예를들어 정점이 6개고 parent 배열이 union(1, 2), union(2, 3) union(3, ..