![]()
17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 문제 섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다. 섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다. 다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 ..
트리(Tree) 그래프의 특수한 경우. 사이클이 없이 모든 정점이 연결되어 있는 그래프. 2개의 노드 사이에 반드시 1개의 간선만을 가짐. 부모-자식 관계가 존재하여 계층형 모델이라고도 함. 최상위에 Root 노드 존재. 스패닝 트리(Spanning Tree) 그래프 내의 모든 정점을 포함하는 트리 그래프의 최소 연결 그래프. 그러므로 간선의 개수는 (V-1)개 (V는 정점의 개수) 스패닝 트리 = 신장 트리 최소 스패닝 트리(MST, Minimum Spanning Tree) 스패닝 트리 중 간선 가중치의 합이 최소가 되는 스패닝 트리 MST를 구하는 알고리즘은 보통 아래의 2가지를 많이 사용 크루스칼 알고리즘 (Kruskal Algorithm) 프림 알고리즘 (Prim Algorithm) 크루스칼 알고..
