기록방

분리 집합(Disjoint Set)은 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는 지를 확인하는 find 연산으로 구성되어 있는 알고리즘이다. union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산 find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산 Union-Find 원리 이해하기 Union-Find를 표현하는 일반적인 방법은 1차원 배열을 이용하는 것 처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 됨 각 노드가 모두 대표 노드이므로 배열은 자신의 인덱스 값으로 초기화 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산을 수행 대표 노드가 아..

👉 문제링크 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 🔸 문제 분석 🔸 n개의 점들 사이에 m개의 선분을 그을 때, 사이클이 생기는 시점을 확인한다. 사이클이 처음 생긴 순서를 출력한다. 사이클이 생기지 않으면 0을 출력한다. 🔸 문제 풀이 🔸 분리 집합(Disjoint Set)을 이용해 사이클이 생기는 시점을 파악한다. 🔸 코드 🔸 import java.io.*; import java.util.StringTokenizer; public class Main { private static int[] ..

👉 문제링크 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 🔸 문제 분석 🔸 문제 내용 N명의 사람과 M개의 파티가 있다. 진실을 아는 사람이 참여한 파티에서는 진실만 말해야 한다. 진실을 말한 파티에 있던 사람들도 진실을 아는 사람이 된다. 거짓을 말할 수 있는 파티의 수를 출력한다. 풀이 전략 같은 파티 참가자를 연결해야 한다. 각 파티별 참가자 List와 개인 별 참가 파티 List를 만든다. BFS로 진실을 말한 파티와 진실을 알게된 사람들을 추가해 나간다. 진실을 말하지 않은 파티의 수를 출력한다. 2024...