그래프115 [백준] 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. [백준] 9372번 - 상근이의 여행 [Java] https://www.acmicpc.net/problem/9372 1. 아이디어 국가를 노드, 비행기의 이동을 간선으로 하는 비행 스케쥴이 연결 그래프를 이룰 때 한 국가에서 다른 모든 국가를 방문하는 최소 비행기들로 이루어진 그래프는 최소 스패닝 트리를 이룬다.2. 문제풀이 최소 스패닝 트리에서 간선의 개수는 (노드의 개수 -1)개임을 이용해서 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Syst.. 2025. 2. 11. [백준] 9466번 - 텀 프로젝트 [Java] https://www.acmicpc.net/problem/9466 1. 아이디어 유방향 그래프에서 사이클에 속하지 않는 학생의 수를 구하는 문제가 된다. DFS 알고리즘과 위상 정렬을 활용하면 해결할 수 있다.2. 문제풀이 DFS는 각 점에 대해 매번 탐색을 하면 중복되는 사이클이 있는 그래프에 반복 접근하게 되고 이 부분에서 시간초과가 발생하게 된다. 이를 방지하기 위해 임시 방문과 실제 방문 두 가지 방문 체크를 활용해서 임시 방문으로 사이클 여부를 파악 후 사이클이 존재하면 사이클의 크기를 구한 후 실제 방문 처리를 하는 방식으로 구현했다. 위상 정렬은 사이클이 존재하면 정렬할 수 없는 점을 활용해서 정렬된 노드의 개수가 사이클을 이루지 못한 학생의 수가 됨을 활용했다.3. 코드 import ja.. 2025. 2. 10. [백준] 9205번 - 맥주 마시면서 걸어가기 [Java] https://www.acmicpc.net/problem/9205 1. 아이디어 상근이네 집과 편의점들, 펜타포트 락 페스티벌을 노드로 각 노드간 거리를 간선으로 하는 그래프에서 두 노드가 연결되었는지 판단하는 문제가 된다. 맥주 1병에 50미터씩 총 1000미터를 한번에 이동할 수 있으므로 간선의 길이가 1000이하인 간선만으로 그래프를 구성한 후 BFS, DFS 알고리즘으로 연결 여부를 파악하면 간단하게 해결할 수 있다.2. 문제풀이 거리가 맨해튼 거리이므로 Math.abs 메서드를 활용했고 상근이네 집을 출발점, 펜타포트 락 페스티벌을 도착점으로 탐색해서 도착할 수 있으면 true, 도착할 수 없으면 false를 반환하는 방식으로 구현했다.3. 코드 import java.io.*;import ja.. 2025. 2. 10. 이전 1 2 3 4 5 ··· 10 다음
