백준/유니온 파인드 (3) 썸네일형 리스트형 [ICPC] 백준 20040 - 사이클 게임 https://www.acmicpc.net/problem/20040 힌트 더보기 유니온 파인드를 사용하면 그래프의 사이클 존재 여부를 빠르게 판별할 수 있다. 풀이 더보기 각 정점을 이어나갈 때 사이클이 어느 순서에 생기는지 알아야 하는 문제이다. 각 정점을 이을 때마다 DFS를 이용한 사이클 검출을 실시하면 $O(m^{2})$의 시간 복잡도로 인해 시간 초과를 받을 것이다. 하지만 유니온 파인드를 이용하면 아주 짧은 시간으로 사이클 여부를 판단할 수 있다. 각 정점을 union 하면서 만약 부모가 같은 정점을 마주치면 트리 상태에서 간선을 한 개 추가하는 것이므로 곧 사이클이 존재하는 그래프가 됨을 알 수 있다. m개의 쿼리를 진행하면서 사이클이 생기는지 검사하도록 하자. 전체 코드 #pragma GC.. [USACO] 백준 1774 - 우주신과의 교감 https://www.acmicpc.net/problem/1774 2021-08-17 기준 한글 번역의 질이 좋지 못하다는 코멘트가 있는 상황이다. 영어로 문제를 읽을 것을 추천한다. 이 문제는 2차원 평면에서 MST(Minimum Spanning Tree)를 완성해야 하는 문제이다. 각 정점이 서로 연결되었을 때의 간선들을 전부 생성해서 적절한 방법으로 MST를 구성하여 얻은 가중치의 합이 정답이 된다. 시간 복잡도는 간선을 생성하는 과정이 dominant factor이므로 $O(N^{2})$이다. 구현 다른 MST 문제와는 달리 2차원 평면이라 구현에 막연함이 있을 수 있다. 우리는 map을 이용하여 각 좌표의 index를 매기고 이 index를 기반으로 유니온 파인드를 만들면 간단하게 구현할 수 있.. 백준 1976 - 여행가자 https://www.acmicpc.net/problem/1976 최대 200개의 도시 수가 인접행렬 형태로 주어진다. 문제에서 주어진 여행지들을 모두 여행할 수 있는지 판단할 것을 요구하고 있다. 즉 주어진 도시들이 연결되었는지를 판단하면 되므로 두가지의 풀이를 생각할 수 있는데 첫번째는 플로이드 워셜 알고리즘을 이용하여 쉽게 구하는 방법이고 두번째는 유니온 파인드를 이용해 각 정점들이 연결되어 있는지 판단하는 방법이다. 이 풀이에서는 유니온 파인드를 이용해보겠다. DisjointSet st(n); int loop; cin >> loop; for (int i = 0; i > connex; if (con.. 이전 1 다음
