돌고 돌아 기본

프로그래머스 42861번 - 섬 연결하기 요구사항 1. 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 반환하라. 2. A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 요구사항 분석 및 풀이과정 1. 이 문제는 전형적인 최소 스패닝 트리 문제입니다. 최소 스패닝 트리 문제는 크루스칼 알고리즘 또는 프림 알고리즘으로 해결 가능합니다. 2. 저는 서로소 집합(Union-Find)을 이용한 크루스칼 알고리즘을 사용할 할 것입니다. 크루스칼 알고리즘에 대해서는 따로 설명하지 않겠습니다. 3. 섬 사이에 다리를 건설하는 비용을 기준으로 내림차순 정렬하여, 비용이 적은 다리부터 사이클이 형성되지 않도록 N - 1 개의 ..

프로그래머스 43162번 - 네트워크 요구사항 1. 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 2. 1번을 만족할 경우 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 말할 수 있습니다. 3. 주어진 연결 정보를 바탕으로 네트워크가 구성되어있을 때, 네트워크의 개수를 반환하라. 요구사항 분석 및 풀이과정 1. 문제가 어려워 보이지만 결과적으로 주어진 컴퓨터들이 몇 개의 그룹으로 묶이는지를 묻는 문제입니다. 2. 전형적인 서로소 집합(Disjoint-Set, Union-Find) 문제라고 볼 수 있습니다. 서로소 집합을 이용하여 풀어보겠습니다. 서로소 집합 자료구조에..

기본적인 구현 class Dsu { private final int[] parent; public Dsu(int size) { this.parent = new int[size]; for (int i = 0; i < size; i++) { parent[i] = i; } } public int find(int x) { if (parent[x] == x) { return x; } parent[x] = find(parent[x]); return parent[x]; } public boolean union(int x, int y) { int parentX = find(x); int parentY = find(y); if (parentX == parentY) { return false; } parent[parent..