반응형 Disjoint set2 [C/C++] 백준 #2468 안전 영역(탐욕 알고리즘) #2468 문제는 그래프 이론, 부르트포스 방법 등으로 풀 수 있겠지만, 전 정렬을 이용한 탐욕 알고리즘을 이용해서 풀었습니다. 어쩌다 보니, 푼 사람 내에서 상위권에 있다보니 제 소스 참조횟수가 많은 문제가 되었네요. https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 제가 생각한 것은 단순합니다. 일단 지대가 높은 것부터 낮은 순으로 정렬을 합니다. 지대가 가장 높은 곳은 비가 가장 많이 왔을 때에도 안전지대가 되겠죠. 그리고 그 영역의 개수는 상호 .. 2023. 5. 16. [C/C++] 백준 #1976 여행 가자(배타적 집합) 이번문제는 도시와 도시간 연결 정보를 알고 있으면, 중간에 다른 도시를 경유해서라도, 원하는 도시들을 여행할 수 있는지를 알아보는 것입니다. 사실 이 문제는 그래프를 만들어서 DFS나 BFS를 통해서 원하는 도시들을 다 방문하는지 찾아보아도 됩니다. 저는 배타적 집합(Disjoint Set)을 이용했습니다. 배타적 집합에서 집합을 찾고 합집합을 하는 것이 모두 상수시간이 걸리기 때문에, 전체적으로 \(O(N^2)\)의 알고리즘 효율로 할 수 있습니다. 연결된 도시가 나타나면, 각각의 도시가 속한 집합을 합집합을 하게 됩니다. 그러면 서로 분리된 한개 이상의 집합들이 나오게 되는데, 여행하고자 하는 도시들이 같은 집합에 있는지 검사하면 됩니다. 제가 작성한 소스입니다. //------------------.. 2022. 12. 20. 이전 1 다음 728x90
