기록방

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

👉 문제링크 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 🔸 문제 분석 🔸 N개의 도시 중 M개의 도시를 여행하고자 한다. 경로가 있어서 여행이 가능하면 YES, 불가능하면 NO를 출력한다. 🔸 문제 풀이 🔸 여행 하고자 하는 M개의 도시 간에 경로가 있는지 파악하는 쉬운 방법은 같은 집합에 있는지 확인하는 것이다. 분리 집합(Disjoint Set)으로 N개의 도시들의 집합을 나눈다. 여행 계획상의 도시들이 같은 집합에 있으면 경로가 존재한다는 뜻이다. 분리 집합이 아니라 BFS나 DFS로 Brute F..

👉 문제링크 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[] ..

👉 문제링크 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 🔸 문제 분석 🔸 N개의 집과 M개의 집 사이를 연결하는 길이 있다. 서로 이어지지 않는 마을 2개를 만드려고 하는데, 각 마을 안에서는 집끼리 길이 연결되어 있어야 한다. 길의 유지비 합의 최소값을 출력한다. 🔸 문제 풀이 🔸 마을 안에서 집 사이에 길이 연결되어 있어야 하고, 그 가중치가 최소가 되어야 하므로, 두 개의 최소 신장 트리(MST) 가 만들어져야 한다. 여기서는 크루스칼(Kruskal) 알고리즘을..

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