백준/유니온 파인드 (3) 썸네일형 리스트형 [ICPC] 백준 20040 - 사이클 게임 https://www.acmicpc.net/problem/20040 힌트 더보기 유니온 파인드를 사용하면 그래프의 사이클 존재 여부를 빠르게 판별할 수 있다. 풀이 더보기 각 정점을 이어나갈 때 사이클이 어느 순서에 생기는지 알아야 하는 문제이다. 각 정점을 이을 때마다 DFS를 이용한 사이클 검출을 실시하면 O(m2)의 시간 복잡도로 인해 시간 초과를 받을 것이다. 하지만 유니온 파인드를 이용하면 아주 짧은 시간으로 사이클 여부를 판단할 수 있다. 각 정점을 union 하면서 만약 부모가 같은 정점을 마주치면 트리 상태에서 간선을 한 개 추가하는 것이므로 곧 사이클이 존재하는 그래프가 됨을 알 수 있다. m개의 쿼리를 진행하면서 사이클이 생기는지 검사하도록 하자. 전체 코드 #pragma GC.. [USACO] 백준 1774 - 우주신과의 교감 https://www.acmicpc.net/problem/1774 2021-08-17 기준 한글 번역의 질이 좋지 못하다는 코멘트가 있는 상황이다. 영어로 문제를 읽을 것을 추천한다. 이 문제는 2차원 평면에서 MST(Minimum Spanning Tree)를 완성해야 하는 문제이다. 각 정점이 서로 연결되었을 때의 간선들을 전부 생성해서 적절한 방법으로 MST를 구성하여 얻은 가중치의 합이 정답이 된다. 시간 복잡도는 간선을 생성하는 과정이 dominant factor이므로 O(N2)이다. 구현 다른 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 다음 1/1
