승코딩당당당

문제[C++] 백준 1976: 여행 가자 GOLD 4https://www.acmicpc.net/problem/1976 접근 방법백준 1976번은 여행 계획이 가능한지 판단하는 문제다.여러 도시가 있고, 도시 간 연결 정보가 주어질 때 주어진 여행 계획대로 모든 도시를 이동할 수 있는지 확인해야 한다. 핵심 아이디어는 다음과 같다.여행 계획에 포함된 모든 도시가하나의 연결된 그룹(같은 집합) 에 속해 있는지 확인하면 된다. 이 문제는 도시 간 연결 여부를 계속 확인해야 하므로Union-Find(Disjoint Set) 자료구조를 사용하는 것이 가장 효율적이다. 상세 아이디어부모 배열 초기화 parent.resize(N + 1, 0);for (int i = 1; i 각 도시는 처음에 자기 자신을 부모로 가..

문제[C++] 백준 1717: 집합의 표현 GOLD 5https://www.acmicpc.net/problem/1707 접근 방법백준 1717번은 집합의 합집합과 포함 여부를 처리하는 문제로,대표적인 Union-Find(Disjoint Set) 자료구조를 사용하는 문제다. 문제에서 수행하는 연산은 두 가지다.0 a b → a와 b를 같은 집합으로 합치기 (Union)1 a b → a와 b가 같은 집합인지 확인 (Find)따라서 핵심은 각 원소가 어떤 집합에 속해 있는지를 효율적으로 관리하는 것이다. 이를 위해 parent 배열을 사용한다.vector parent; parent[i] : i의 부모 노드초기에는 모든 원소가 자기 자신을 부모로 가진다.for (int i = 1; i Find (대표 노드 ..