분리 집합4 [백준] 1717번 - 집합의 표현 [Java] https://www.acmicpc.net/problem/1717 1. 아이디어 유니온 파인드 알고리즘으로 해결할 수 있다.2. 문제풀이 각 집합의 합집합 연산은 union, 같은 집합에 있는 지 확인하는 연산은 find로 구할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { private static int[] p; private static int[] make(int N) { int[] arr = new int[1 + N]; for (int i = 1; i 4. 후기 2025. 3. 20. [백준] 1976번 - 여행 가자 [Java] https://www.acmicpc.net/problem/1976 1. 아이디어 여행을 가려는 도시가 모드 하나의 그래프 안에만 있으면 되므로 유니온 파인드 알고리즘으로 해결할 수 있다.2. 문제풀이 union 연산으로 그래프를 구성한 후 Set을 활용해 여행가려는 각 도시의 그룹장을 저장했다.Set의 크기가 1이면 모든 도시가 하나의 그래프 안에 있는 것이므로 여행을 갈 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { private static int[] p; private static int[] make(int N) { int[] arr = new int[1 + N]; for (int i = .. 2025. 3. 20. [백준] 1043번 - 거짓말 [Java] https://www.acmicpc.net/problem/1043 1. 아이디어 유니온 파인드 알고리즘을 통해 각 파티를 집합으로 표현한 후 각 파티의 그룹장만 따로 담아준다.이후 각 파티의 그룹장이 진실을 아는 지 판단했다.2. 문제풀이 진실을 아는 사람은 부모의 번호를 0번으로 설정했고 파티의 그룹장은 번호가 작은 사람이 오도록 했다.유니온 파인드 알고리즘을 통해 그룹을 형성한 후 그룹장만 따로 Queue에 담아줬다.이러면 Queue의 그룹장의 부모(최고 조상)이 0인지 여부로 그룹에 진실을 말해야하는지 간단하게 판단할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { private static int[] p; priv.. 2025. 3. 20. [백준] 11724번 - 연결 요소의 개수 [Java] https://www.acmicpc.net/problem/11724 1. 아이디어 주어진 입력으로 만들어질 수 있는 그래프의 개수를 구하는 문제로 BFS, DFS, Union-Find 알고리즘 3가지 방법으로 해결할 수 있었다.2. 문제풀이 BFS와 DFS는 주어진 입력으로 그래프의 연결관계를 나타내는 인접리스트와 각 정점을 방문했는지 표시하는 방문 체크 배열을 만든 후 반복문으로 각 정점을 순회하며 방문한 정점이면 넘어가고 방문하지 않은 정점이면 탐색으로 그래프의 개수를 세는 방식으로 구현했다. Union-Find는 인접리스트를 만드는 대신 바로 집합 연결을 해주었다. 이후 각 정점이 집합의 그룹장인지 여부만 세면 간단하게 그래프의 개수를 구할 수 있다.3. 코드 import java.io.*;im.. 2025. 1. 17. 이전 1 다음
