반응형 분리집합7 백준 1939번 중량제한 - C++ 풀이 1. 가중치 내림차순으로 간선을 정렬한다. 2. 두 공장이 이어질 때까지 간선을 하나씩 추가한다. 1. 가중치 내림차순으로 간선을 정렬한다. 시작 공장에서 도착 공장으로 가는 경로에서 가중치가 가장 작은 간선이 한 번에 옮길 수 있는 중량의 최댓값을 결정한다. 2. 두 공장이 이어질 때까지 간선을 하나씩 추가한다. 따라서 시작 공장에서 도착 공장으로 가는 경로가 생성될 때까지 가중치가 큰 간선부터 차례로 추가해보면 된다. 가중치가 큰 순서로 추가했으므로, 최초로 경로가 만들어지는 순간에 추가한 간선이 경로 내에서 최소 가중치를 갖는 간선이 되므로 해당 간선의 가중치가 답이 된다. #include #include using namespace std; typedef pair pii; typedef pair .. 2022. 8. 12. 백준 14890번 경사로 - 스위프트(Swift) 풀이 + 그림 설명 1. 한 길 내에서 인접한 같은 높이의 칸들을 union 한다. 이때 각 집합의 크기를 기록해둔다. 2. 한 길 내의 모든 칸을 순회하면서 다음 칸으로 갈 수 있는지 체크한다. 2-1. 다음 칸과의 높이가 1 차이나고, 더 낮은 칸이 속한 집합의 크기가 L 이상이라면 경사로를 놓아서 갈 수 있다. 2-2. 다음 칸과 높이가 같다면 그냥 갈 수 있다. 2-3. 그 외의 경우에는 갈 수 없다. 1. 한 길 내에서 인접한 같은 높이의 칸들을 union 한다. 이때 각 집합의 크기를 기록해둔다. 인접한 같은 높이의 칸은 이동할 수 있다. 몇 개가 연속해서 같은 높이인지 쉽게 파악하기 위해 union 하면서 집합의 크기를 기록한다. 2. 한 길 내의 모든 칸을 순회하면서 다음 칸으로 갈 수 있는지 체크한다. 2-.. 2022. 2. 10. 백준 2162번 선분 그룹 - 스위프트(Swift) 풀이 1. 모든 선분 쌍에 대해 두 선분이 서로 만난다면 union 한다. 2. union 과정에서 집합의 크기를 기록한다. 3. 전체 집합의 개수와 가장 큰 집합의 크기를 출력한다. 1. 모든 선분 쌍에 대해 두 선분이 서로 만난다면 union 한다. 서로 만나는 두 선분을 같은 그룹으로 묶어주어야 한다. 유니온 파인드의 union 연산을 해준다. 선분 교차 알고리즘은 17387번에서 썼던 걸 그대로 썼다. 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 2. union 과정에서 집합의 크기를 기록한다. 마지막에 가장 큰 그룹의 크기를 출력해야 하기 때문에 union 과정에.. 2022. 2. 7. 백준 16946번 벽 부수고 이동하기 4 - 스위프트(Swift) 풀이 + 그림 설명 1. DFS를 돌면서 인접한 빈칸들을 union 한다. 2. union 할 때 각 집합의 크기를 기록해둔다. 3. 각 벽마다 상하좌우의 빈칸 집합의 크기를 더한다. 1. DFS를 돌면서 인접한 빈칸들을 union 한다. 빈칸들이 인접해있으면 인접한 빈칸을 모두 방문할 수 있다. 따라서 인접한 빈칸들을 유니온 파인드를 사용해 하나의 집합으로 처리해준다. 2. union 할 때 각 집합의 크기를 기록해둔다. 방문할 수 있는 빈칸의 개수를 알아야 하기 때문에 각 집합의 크기를 구해둬야 한다. 두 집합을 union 할 때 크기도 같이 합쳐서 기록해두자. 3. 각 벽마다 상하좌우의 빈칸 집합의 크기를 더한다. 어떤 벽을 부수면, 벽 때문에 막혀있던 상하좌우 칸들이 연결되게 된다. 따라서 어떤 벽을 부쉈을 때 방문.. 2022. 2. 5. 백준 16724번 피리 부는 사나이 - 스위프트(Swift) 풀이 + 그림 설명 1. DFS를 돌면서 이어져있는 칸들을 Union한다. 각 집합마다 SAFE ZONE은 한 개만 있으면 된다. 2. 이미 방문한 점이더라도 Union은 하고 넘어간다. 3. 집합의 개수가 곧 SAFE ZONE의 개수이다. 1. DFS를 돌면서 이어져있는 칸들을 Union한다. 각 집합마다 SAFE ZONE은 한 개만 있으면 된다. 어떤 칸들이 하나의 경로로 이어져있다면 결국 경로 중 어느 칸에서 출발하더라도 계속 가다 보면 그 경로의 끝 칸에 도달하게 된다. 따라서 그 끝 칸에만 SAFE ZONE을 설치하면 된다. 한 경로로 이어져 있는 칸들을 하나의 집합으로 처리하기 위해 유니온 파인드를 사용한다. DFS를 돌면서 한 경로로 이어져있는 칸들을 모두 union 해준다. 2. 이미 방문한 점이더라도 Uni.. 2022. 2. 5. 이전 1 2 다음 반응형
