최소 스패닝 트리15 [백준] 17472번 - 다리 만들기 2 [Java] https://www.acmicpc.net/problem/17472 1. 아이디어 BFS, DFS 알고리즘으로 각 섬에 대해 번호를 매긴 후 설치할 수 있는 모든 다리를 찾아서 섬은 노드, 다리를 간선으로 하는 최소 스패닝 트리를 구하는 방식으로 해결했다.2. 문제풀이 각 섬에 번호를 붙여서 섬들을 구분하려고 했고 지도를 순회하며 섬을 발견하면 BFS, DFS 알고리즘으로 해당 섬 전체에 번호를 부여했다. 이후 지도를 순회하며 현재 위치가 섬이면서 오른쪽이 바다인 경우, 현재 위치가 섬이면서 아래쪽이 바다인 경우, 다시 섬을 발견할 때까지 해당 방향으로 계속 가며 섬을 발견하면 이 정보로 다리를 생성해서 우선순위 큐에 넣어줬다. 이후 이 우선순위 큐로 크루스칼 알고리즘을 돌려 모든 섬을 연결하는 다리 .. 2025. 2. 11. [백준] 2887번 - 행성 터널 [Java] https://www.acmicpc.net/problem/2887 1. 아이디어 행성을 노드, 연결을 간선으로 하는 최소 스패닝 트리를 구하는 문제가 된다. N개의 행성에서 나올 수 있는 모든 연결은 총 N * (N-1) / 2개로 N이 최대 10만이라면 너무 많은 경우가 나오게 된다. 최소 스패닝 트리는 N-1개의 간선만 선택하면 되는데 이때 특정 축에 대해 좌표를 정렬한 후 서로 인접한 행성끼리 연결한다고 했을 때 N-1개의 연결이 나오고 이 연결로도 최소 스패닝 트리를 만들 수 있다.(인접하지 않은 행성들은 이 연결들로 찾으면 된다.) 따라서 각 축에 대해 모두 구한 3 * (N-1)개의 간선만으로 전체 행성에 대한 최소 스패닝 트리를 구할 수 있다.2. 문제풀이 행성 번호와 좌표를 담은 2차원 .. 2025. 2. 11. [백준] 16398번 - 행성 연결 [Java] https://www.acmicpc.net/problem/16398 1. 아이디어 행성을 노드, 플로우를 간선으로 하는 최소 스패닝 트리를 구하는 문제가 된다.2. 문제풀이 크루스칼 알고리즘으로 최소 스패닝 트리를 구하는 방식으로 구현했다. 이때 N이 1이 될 수 있는 점과 가중치의 합이 int형 오버플로우가 발생할 수 있는 점에 주의해야했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static class Edge implements Comparable { int a; int b; int w; public Edge(int a, int b, int w) { .. 2025. 2. 11. [백준] 10423번 - 전기가 부족해 [Java] https://www.acmicpc.net/problem/10423 1. 아이디어 도시를 노드, 케이블을 간선으로 하는 최소 스패닝 트리들로 구성시키는 문제로 각 최소 스패닝 트리에 발전소가 하나만 있게 해야한다. 이를 위해 각 최소 스패닝 트리의 그룹장이 항상 발전소가 되도록 크루스칼 알고리즘으로 구현했다.2. 문제풀이 발전소가 위치한 도시는 Set에 별도로 저장한 후 크루스칼 알고리즘을 사용했다. 크루스칼 알고리즘에서 해당 케이블에 연결된 두 도시의 그룹장을 뽑아서 둘이 일치하거나(싸이클이 생김) 둘 다 발전소가 설치됐으면 넘어가고 한쪽만 발전소가 설치됐으면 발전소가 설치된 쪽이 그룹장이 되도록 유니온을 했다. 둘 다 발전소가 설치가 안됐으면 아무쪽이나 연결해도 된다.(간선 선택이 끝나면 발전소가 .. 2025. 2. 11. [백준] 1368번 - 물대기 [Java] https://www.acmicpc.net/problem/1368 1. 아이디어 해당 논에 우물을 파는 것을 해당 논에서 가상의 0번 논에 물을 끌어오는 것으로 가정했을 때 가상의 0번 논을 포함한 모든 논을 연결하는 최소 스패닝 트리를 구하는 문제가 된다.2. 문제풀이 크루스칼 알고리즘으로 최소 스패닝 트리를 구하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static class Edge implements Comparable { int a; int b; int w; public Edge(int a, int b, int w) { .. 2025. 2. 11. [백준] 13418번 - 학교 탐방하기 [Java] https://www.acmicpc.net/problem/13418 1. 아이디어 입구와 건물을 노드, 길을 간선으로 생각했을 때 모든 건물을 연결하는 경우 피로도의 최솟값은 최소 스패닝 트리로, 피로도의 최댓값은 최대 스패닝 트리로 구할 수 있다. 간선의 정렬 기준을 역순으로 해주는 것으로 최대 스패닝 트리도 간단하게 구할 수 있는 점을 활용했다.2. 문제풀이 크루스칼 알고리즘으로 최소 스패닝 트리를 구하는 방식으로 구현했다. 오르막길은 0, 내리막길은 1로 입력이 주어지는 점만 주의해서 구현하면 된다.3. 코드 import java.io.*;import java.util.*;public class Main { private static class Edge { int a; .. 2025. 2. 11. [백준] 6497번 - 전력난 [Java] https://www.acmicpc.net/problem/6497 1. 아이디어 집을 노드, 길을 간선으로 생각했을 때 모든 집을 연결하는 경우는 최소 스패닝 트리가 될 때이다. 처음 불이 켜진 길의 비용 합을 미리 구한 후 최소 스패닝 트리의 가중치를 빼면 절약할 수 있는 최대 비용을 구할 수 있다.2. 문제풀이 크루스칼 알고리즘으로 최소 스패닝 트리를 구하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static class Edge implements Comparable { int a; int b; int w; public Edge(int a, .. 2025. 2. 11. [백준] 1774번 - 우주신과의 교감 [Java] https://www.acmicpc.net/problem/1774 1. 아이디어 우주신을 노드, 통로를 간선으로 생각했을 때 빵상을 만드는 경우는 최소 스패닝 트리가 될 때이다. 유니온 파인드 알고리즘으로 미리 연결된 우주신 정보를 통해 연결을 한 후 크루스칼 알고리즘을 활용해서 해결했다.2. 문제풀이 Math.sqrt 메서드와 Math.pow 메서드로 거리를 구한 후 이를 활용해 간선 정보로 사용했다. 이미 연결된 통로를 유니온 파인드 알고리즘으로 연결 후 연결된 개수를 저장해서 이후 크루스칼 알고리즘을 적용할 때 추가로 연결해야하는 간선 개수 정보에 활용했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static.. 2025. 2. 11. [백준] 4386번 - 별자리 만들기 [Java] https://www.acmicpc.net/problem/4386 1. 아이디어 별을 노드, 선을 간선으로 생각했을 때 별자리를 최소 비용으로 만드는 경우는 최소 스패닝 트리가 될 때이다. 별의 좌표로 거리를 구한 후 크루스칼 알고리즘을 활용해서 해결했다.2. 문제풀이 Math.sqrt 메서드와 Math.pow 메서드로 거리를 구한 후 이를 활용해 간선 정보로 사용했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static class Edge implements Comparable { int a; int b; double w; public Edge(int a, int.. 2025. 2. 11. [백준] 21924번 - 도시 건설 [Java] https://www.acmicpc.net/problem/21924 1. 아이디어 건물을 노드, 도로를 간선으로 생각했을 때 모든 건물이 도로를 통해 연결되도록 최소한의 도로로 만드는 것은 최소 스패닝 트리를 구하는 문제가 된다. 전체 비용에서 최소 스패닝 트리의 비용을 빼면 절약하는 비용이 된다.2. 문제풀이 입력에서 전체 비용을 미리 계산 후 크루스칼 알고리즘으로 최소 스패닝 트리의 비용을 구하는 방식으로 구현했다. 이때 모든 건물이 연결되지 않으면 -1을 출력하기 위해 간선의 개수가 노드의 개수 - 1 이 되지 않으면 -1을 반환하도록 했다. 도로 비용의 합이 int형 범위를 넘어갈 수 있음에 주의해야 한다.3. 코드 import java.io.*;import java.util.*;public c.. 2025. 2. 11. [백준] 1922번 - 네트워크 연결 [Java] https://www.acmicpc.net/problem/1922 1. 아이디어 선은 두 컴퓨터에 대한 양방향 연결이 되고 컴퓨터와 컴퓨터를 연결하는 선에 대해 모든 컴퓨터를 연결하는 최소 비용을 구하는 문제로 최소 스패닝 트리를 구하는 문제가 되고 크루스칼 알고리즘을 활용해서 해결했다.2. 문제풀이 유니온 파인드 알고리즘을 활용한 분리 집합과 우선순위 큐를 활용한 간선 정렬로 크루스칼 알고리즘을 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static class Edge implements Comparable { int a; int b; int w; publ.. 2025. 2. 11. [백준] 1197번 - 최소 스패닝 트리 [Java] https://www.acmicpc.net/problem/1197 1. 아이디어 최소 스패닝 트리의 가중치를 구할 수 있는 크루스칼 알고리즘을 활용해서 해결했다.2. 문제풀이 유니온 파인드 알고리즘을 활용한 분리 집합과 우선순위 큐를 활용한 간선 정렬로 크루스칼 알고리즘을 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static class Edge implements Comparable { int a; int b; int w; public Edge(int a, int b, int w) { this.a = a; this.b.. 2025. 2. 11. 이전 1 2 다음
