넘치게 채우기

https://leetcode.com/problems/redundant-connection/description/leetcode - Redundant Connection문제 유형: 유니온-파인드, 분리 집합문제 난이도: Medium 문제In this problem, a tree is an undirected graph that is connected and has no cycles.You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was no..

https://leetcode.com/problems/make-lexicographically-smallest-array-by-swapping-elements/description/leetcode - Make Lexicographically Smallest Array by Swapping Elements문제 유형: 우선순위큐, 유니온-파인드문제 난이도: Medium 문제You are given a 0-indexed array of positive integers nums and a positive integer limit.In one operation, you can choose any two indices i and j and swap nums[i] and nums[j] if |nums[i] - num..

https://www.acmicpc.net/problem/20303BOJ - 할로윈의 양아치문제 유형: 유니온-파인드, 다이나믹 프로그래밍, 배낭 문제문제 난이도: Gold III시간 제한: 1초메모리 제한: 1024MB 문제Trick or Treat!!10월 31일 할로윈의 밤에는 거리의 여기저기서 아이들이 친구들과 모여 사탕을 받기 위해 돌아다닌다. 올해 할로윈에도 어김없이 많은 아이가 할로윈을 즐겼지만 단 한 사람, 일찍부터 잠에 빠진 스브러스는 할로윈 밤을 즐길 수가 없었다. 뒤늦게 일어나 사탕을 얻기 위해 혼자 돌아다녀 보지만 이미 사탕은 바닥나 하나도 얻을 수 없었다.단단히 화가 난 스브러스는 거리를 돌아다니며 다른 아이들의 사탕을 빼앗기로 마음을 먹는다. 다른 아이들보다 몸집이 큰 스브러스에..

https://www.acmicpc.net/problem/20040BOJ - 사이클 게임문제 유형: 유니온-파인드, 트리, 서로소-집합문제 난이도: Gold IV시간 제한: 1초메모리 제한: 512MB 문제사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 번호가 부여된 평면 상의 점 n 개가 주어지며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 매 차례 마다 플레이어는 두 점을 선택해서 이를 연결하는 선분을 긋는데, 이전에 그린 선분을 다시 그을 수는 없지만 이미 그린 다른 선분과 교차하는 것은 가능하다. 게임을 진행하다가 처음으로 사이클을 완성하는 순간..

https://www.acmicpc.net/problem/11779BOJ - 최소비용 구하기 2문제 유형: 최단 거리, 다익스트라, 유니온-파인드문제 난이도: Gold III시간 제한: 1초메모리 제한: 256MB 문제n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다. 입력첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄..

https://www.acmicpc.net/problem/1043BOJ - 거짓말문제 유형: 유니온-파인드, BFS, DFS, 그래프 문제 난이도: Gold IV 시간 제한: 2초 메모리 제한: 128MB 문제지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히,..

https://leetcode.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/description/leetcode - Remove Max Number of Edes to Keep Graph Fully Traversable문제 유형 : 유니온-파인드, 그리디문제 난이도 : Hard 문제Alice and Bob have an undirected graph of n nodes and three types of edges:Type 1: Can be traversed by Alice only.Type 2: Can be traversed by Bob only.Type 3: Can be traversed by both Alice and..