반응형 배타적 집합2 [C/C++] 백준 #1976 여행 가자(배타적 집합) 이번문제는 도시와 도시간 연결 정보를 알고 있으면, 중간에 다른 도시를 경유해서라도, 원하는 도시들을 여행할 수 있는지를 알아보는 것입니다. 사실 이 문제는 그래프를 만들어서 DFS나 BFS를 통해서 원하는 도시들을 다 방문하는지 찾아보아도 됩니다. 저는 배타적 집합(Disjoint Set)을 이용했습니다. 배타적 집합에서 집합을 찾고 합집합을 하는 것이 모두 상수시간이 걸리기 때문에, 전체적으로 \(O(N^2)\)의 알고리즘 효율로 할 수 있습니다. 연결된 도시가 나타나면, 각각의 도시가 속한 집합을 합집합을 하게 됩니다. 그러면 서로 분리된 한개 이상의 집합들이 나오게 되는데, 여행하고자 하는 도시들이 같은 집합에 있는지 검사하면 됩니다. 제가 작성한 소스입니다. //------------------.. 2022. 12. 20. [C/C++] 백준 #1717 집합의 표현(배타적 집합) 이번 문제는 배타적 집합(disjoint set)의 전형적인 예입니다. 배타적 집합이라는 것은 임의의 원소가 어느 하나의 집합에만 속해있는 경우입니다. 어떤 원소도 두개 이상의 집합에 속해있지 않기 때문에 일반적으로 사용하는 집합과는 다릅니다. 달리 말하면 임의의 두개의 다른 집합의 교집합은 항상 공집합이라 할 수 있습니다. 아래의 그림과 같이, 왼쪽은 배타적 집합입니다. 두 집합 A, B에 공통된 원소가 존재하지 않습니다. 그에 비해 일반 집합은 공통된 원소가 존재할 수 있습니다. 일번적으로 배타적 집합은 배열을 이용하게 됩니다. 보통은 함수를 이용해서 축약까지 넣는데, 축약을 넣지 않은 상태에서도 테스트가 통과해서 그대로 적용했네요. 축약을 사용하는 경우에는 다음과 같이 처리합니다. int getRo.. 2022. 10. 2. 이전 1 다음 728x90
