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/1944 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 난이도 : 골드 1 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 최소 스패닝 트리 설명 문제를 보고, BFS로 각 키-키, 로봇-키의 최단거리를 얻어야겠다는 생각은 빨리 떠올랐는데, 최소 이동거리를 어떻게 구해야 하나 고민을 좀 했던 문제였습니다. 결국 태그를 슬며시 눌러봤는데, '최소 스패닝 트리' 키워드를 보고 아 맞네...!를 외쳤습니다...ㅎㅎ.....

https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 난이도 : 골드 3 태그 : 그래프 이론, 최소 스패닝 트리 설명 모든 별을 선으로 이어 별자리를 만드는 문제입니다. 별자리를 잇는다는 건, 두 별을 직선으로 이은 것이며, 모든 별자리는 직/간접적으로 서로 이어져 있어야 합니다. 별을 이을 때 거리만큼의 비용이 들 때, 모든 별을 직/간접적으로 이으면서 그 비용이 최소가 되는 경우를 찾아야 합니다. "모든 별(노드)를 선으로 직/간접적으로 이으면서..

https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번 www.acmicpc.net 난이도 : 골드 3 태그 : 그래프 이론, 최소 스패닝 트리 설명 최소 스패닝 트리를 응용하여 각 간선의 최소값을 구하면서, 최대 스패닝 트리를 구해 각 간선의 최댓값을 구하는 문제입니다. 최대 스패닝 트리의 경우, 최소 스패닝 트리에서 단순히 정렬 조건만 반대로 지정하여 한 번 더 수행하면 구할 수 있습니다. 최소 스패닝 트리를 잘 모르신다면 아래 포스팅을 참..

https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 난이도 : 골드 1 태그 : 구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색, 최소 스패닝 트리 설명 DFS / BFS를 사용해 각 섬을 그룹화 해줍니다. 그리고 각 섬의 모든 점들을 저장해 놨다가, 상하좌우로 방향으로 다리를 만들 수 있는지 확인합니다. 상하좌우 방향으로 현재의 섬을 만난다면 다리를 만들 수 없으며, 다른 섬을 만나..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 최소 스패닝 트리 설명 최소 스패닝 트리의 입문 문제입니다. 응용문제가 아니기에, 연습용으로 제격인 문제네요. 최소 스패닝 트리를 모르신다면 아래 포스팅을 참고해주세요. https://uknowblog.tistory.com/294 [알고리즘] 최소 스패닝 트리 (MST, Minimum Spanning Tree..

https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 난이도 : 골드 3 태그 : 그래프이론, 최소 스패닝 트리, 문자열 설명 몇 가지 기믹이 들어간 최소 스패닝 트리 문제입니다. 해당 문제는 랜선을 가장 많이 기부할 수 있는 길이를 찾는 문제입니다. 따라서, 다솜이가 쓸 랜선은 냅두고, 남은 랜선을 줘야 하는데요. 컴퓨터는 연결된 다른 컴퓨터를 타고 들어가 네트워크를 사용할 수 있으므로, 전체 랜선의 길이에서 최소 스패닝 트리의 가중치의 합을..

최소 스패닝 트리 / 최소 신장 트리 (MST, Minimun Spanning Tree) 스패닝 트리 / 신장 트리는 모든 정점(Vertex, Node)을 간선(Edge)로 사이클이 생기지 않게 연결한 그래프입니다. 최소 스패닝 트리 / 최소 신장 트리는 신장 트리 중에서도 간선의 총 비용이 최소가 되는 트리 입니다. 각 노드와 노드간의 간선이 위와 같이 주어졌습니다. 그럼, 이 위 그래프에서 모든 노드가 이어져 있으면서, 간선의 합이 최소가 되려면 어떤 간선을 선택해야 할까요? 빨간색으로 칠한 간선들을 선택한다면, 간선의 비용을 최소로 하면서 모든 노드를 연결할 수 있습니다. 위 형태가 해당 그래프의 최소 스패닝 트리가 됩니다. 물론, 그래프에 따라 비용이 최소가 되는 스패닝 트리는 여러개 있을 수 있..