https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 난이도 : 골드 3 태그 : 자료 구조, 그래프 이론, 그래프 탐색, 이분 탐색, 너비 우선 탐색, 분리 집합 설명 N개의 섬들은 M개의 다리를 통해 서로 연결 되어있습니다. 각 다리에는 중량 제한이 있고, 중량 제한을 초과할 경우 다리가 무너집니다. 한 번에 이동할 수 있는 중량의 최댓값을 구하는 문제입니다. 가장 빨리 떠오른 생각은 브..

https://www.acmicpc.net/problem/10216 10216번: Count Circle Groups 백준이는 국방의 의무를 수행하기 위해 떠났다. 혹독한 훈련을 무사히 마치고 나서, 정말 잘 생겼고 코딩도 잘하는 백준은 그 특기를 살려 적군의 진영을 수학적으로 분석하는 일을 맡게 되었 www.acmicpc.net 난이도 : 골드 4 태그 : 자료 구조, 그래프 이론, 그래프 탐색, 기하학, 분리 집합 설명 통신 범위가 직/간접적으로 겹치는 부대는 하나의 부대처럼 행동합니다. 즉, 통신범위가 겹치는 그룹을 모두 같은 그룹으로 묶어 몇 개의 그룹이 나오는지 구하는 문제입니다. 그룹화와 서로 다른 그룹의 개수를 구한다는 점에서 분리집합과 유니온 파인드를 사용할 수 있을 것 같습니다. 분리 집..

https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 난이도 : 골드 4 태그 : 자료구조, 그래프이론, 그래프탐색, 분리집합 설명 친구의 친구는 나에게도 친구이므로, 한 친구만 만들면 해당 친구가 속한 그룹은 모두 내 친구가 되므로, 그룹 당 친구비가 가장 적은 친구와 친구를 맺으면 됩니다. 접근방법 1. 분리집합 (유니온 - 파인드)를 사용해 각 친구관계를 그룹화한다. 2. 각 ..

https://www.acmicpc.net/problem/13905 13905번: 세부 첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄 www.acmicpc.net 난이도 : 골드 4 태그 : 자료 구조, 그래프 이론, 그래프 탐색, 분리 집합, 최소 스패닝 트리 설명 한 섬에서 다른 섬으로 가지만, 다리(간선)가 버틸 수 있는 문제가 한정되어 있어, 가중치의 최솟값이 최대가 되야 합니다. 가중치의 최솟값이 최대가 되야 한다... 이게 무슨 말인가 싶긴 하지만, 위 그래프를 예시로 들 때, 1번 집에서 5번 집으로 가..

https://www.acmicpc.net/problem/14868 14868번: 문명 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 세계의 크기를 나타내는 정수 N(2 ≤ N ≤ 2,000)과 문명 발상지의 수 K(2 ≤ K ≤ 100,000)가 주어진다. 다음 K줄에는 한 줄에 하나씩 문명 발상지 www.acmicpc.net 난이도 : 플래티넘 4 태그 : 자료 구조, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 분리 집합 설명 문명은 인접한 칸으로 세력을 넓힙니다. 세력을 넓히면서 한 칸을 서로 차지하려 할 때 혹은 서로 맞닿을 때 두 문명은 합쳐집니다. 한 칸을 서로 차지하려 할 때는 BFS 탐색 중 쉽게 알 수 있으나, 인접할 경우에는 4방향 BFS를 한 번 더 돌려 확인할 수 있습니다..

https://www.acmicpc.net/problem/2610 2610번: 회의준비 첫째 줄에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이 www.acmicpc.net 난이도 : 골드 2 태그 : 그래프 이론, 자료 구조, 그래프 탐색, 분리 집합, 플로이드–워셜 설명 다소 복잡한 문제라, 지문을 두 세번 정도 정독했던 것 같네요. 서로 알고 있는 사람들의 관계가 주어질 때, 서로 알고 있을 경우 무조건 같은 위원회지만, 위원회는 최대한 많아야 하므로, 서로 알고 있지 않을 경우 무조건 다른 위원회로 분리합니다. 위의 말은 최댓값이... 최소가 된다...?는 ..

https://www.acmicpc.net/problem/20955 20955번: 민서의 응급 수술 민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서 www.acmicpc.net 난이도 : 골드 4 태그 : 자료구조, 그래프 이론, 분리집합, 트리 설명 각 뉴런은 시냅스로 연결됩니다. 뉴런은 노드(Node) 혹은 정점(Vertex), 시냅스는 간선(Edge)로 볼 수 있겠습니다. 모든 뉴런이 시냅스로 연결되면서 사이클이 없어야 하는 트리(사이클이 없는 연결 그래프) 구조여야 합니다. 사이클이 생기지 않으면서, 각 노드를 간선으로 병합하는 과정에서는 분리집합 - 유니온파인..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 난이도 : 골드 4 태그 : 자료 구조, 분리 집합, 그래프 이론, 그래프 탐색 설명 이미 갔던 도시를 또 다시 방문 및 경유하여 다른 도시로 가도 되므로, 가려고 하는 도시끼리 모두 이어져있는지 (같은 그룹에 있는지) 판단하면 될 것 같습니다. 이 문제에는 분리집합 알고리즘이 유용하게 쓰일 것 같네요. 분리집합 알고리즘을 모르신다면 아래 포스팅을 참고해주세요. https://uknowblog.t..

분리집합? 분리집합이란 서로소 집합이라고도 불립니다. 이름에서도 알 수 있듯, 각각의 집합이 공통 원소를 가지지 않는 집합입니다. 즉 전체 집합 U에 두 개의 집합 A, B가 있을 때 A ∩ B = Ø 가 성립됩니다,. 이는 집합이 두 개가 아닌 세 개 이상이여도 마찬가지로, 각각의 집합이 공통원소를 가지지 않습니다. Union - Find 이러한 분리집합의 구현과 연산은 Union - Find로 이루어집니다. 말 그대로, Union(병합), Find(찾기) 인데요. 두 개의 트리셋 A와 B가 있다고 합시다. A와 B의 자식노드들은 모두 루트(최상위 노드)를 가리키고 있습니다. 그렇다면, 이 트리 두개를 병합하려면 어떻게 해야 할까요? 바로 B의 루트가 A의 루트를 가리키게 하면 됩니다. 각 트리셋의 자..

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 난이도 : 골드 4 태그 : 자료 구조, 분리 집합 설명 0 a b 일때는 a와 b를 합집합하고, 1 a b 일때는 a와 b가 같은 집합에 속하는지 확인하는 문제입니다. 즉, 원소들간에 그룹을 만들고, 그룹을 하나씩 합쳐가며, 1 연산일때 두 원소가 같은 그룹 내에 존재하는지 확인하면 됩니다. 해당 문제는 분리 집합과 Union - Find 알고리즘을 사용..