MST

[python3] 백준 1939 풀이 ( 중량제한, MST, 유니온 파인드 )

문제를 읽어보면 생각보다 간단하다. 여러개의 섬으로 이루어진 나라가 존재한다. 그리고 2개의 공장이 각 섬에 하나씩 존재한다. 섬들은 서로 중량제한이 있는 다리로 이루어져있다. 따라서 중량제한을 넘지 않고 다리를 건너서 한공장에서 다른 공장으로 물품을 이송해야한다. 이때 공장A에서 공장B로 갈때 얼마나 많은 물품을 한번의 이동시 옮길 수 있는지 출력해야한다. 여기까지 읽고나면 그래프 문제라는 감이 온다. 그런데 A공장에서 B공장까지 가야하기 때문에 여러개의 경로가 존재한다.문제는 다리개수가 100,000개이기 때문에 완탐으로 푸는 미친짓을 해서는 안된다. 천천히 고민해보자 우선 다리를 건너는 비용은 문제가 되지 않는다. A->B로 가기만 하면되고 이때 건너는 다리의 중량한계의 최솟값이 가장 큰 경로를 찾..

[python3] 프로그래머스 섬 연결하기 ( 그리디, MST, 크루스칼, 유니온 파인드)

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 처음에는 그래프 알고리즘을 고민했다. 다익스트라,플로이드를 떠올렸지만 이건 목적지가 존재하는 경우에 사용하는 알고리즘이라 사용불가능 했다. 그러다가 가중치를 기준으로 정렬하여 하나씩 포함하면 되지 않을까 했고 visited 배열을 만들어 노드를 체크해주었다. def solution(n, costs): answer = ..

[c++] 백준 1197 풀이 (MST, 최소 신장 트리, 그래프, 유니온 파인드)

이번에는 MST를 풀어보자. MST는 Minimum Spanning Tree의 약자로 span이란 기간을 의미해서 직역하면 최소화된 기간 트리이다. 좀 더 풀어 말하면 트리가 낮은 가중치로 연결되어 있다고 볼 수 있다. 다르게는 그래프의 최소 연결 부분 그래프 라고 할 수 있다. 이번 문제를 풀기 위해서는 MST를 알기 이전에 Spanning Tree에 대해서 이해해야한다. Spanning Tree 간선 수가 가장 작게 연결된다. 만약 정점이 V개라면 V-1개로 연결된 트리 사이클이 존재하지 않는다.(트리의 형태) Minimum Spanning Tree 값이 가장 작은 간선을 이용하여 만든 Spanning Tree 간선 가중치 합이 최소여야 한다. 사이클이 존재하지 않는다. 크루스칼 알고리즘과 프림알고리..