개발하는 고라니

크루스칼(Kruskal) 알고리즘 이 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 사이클(Cycle)을 만들지 않는 범위에서 최소 비용 간선(Edge)을 하나씩 더해가며 최소 신장 트리(Minimum Spanning Tree, MST)를 만든다. 실제로 여러 도시가 있을 때 각 도시를 도로로 연결하는데 최소 비용을 들여 연결할 때 사용될 수 있는 알고리즘이다. n개의 정점으로 트리를 만드는데 n-1개의 간선이 필요하므로, 처음에 간선이 없는 상태에서 시작하여 n-1개의 간선을 더하는 것이다. 크루스칼 알고리즘은 프림 알고리즘 처럼 하나의 트리를 키워나가는 방식이 아니고, 임의의 시점에 최소 비용의 간선을 더하므로 여러 개의 트리가 산재하게 된다. 크루스칼은 시작점을 정..

2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net # 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 ..