devlog

문제 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 해설 다리만들기 문제는 BFS와 MST 을 만드는 알고리즘을 이용해서 문제를 해결 할 수 있습니다. MST를 만드는 알고리즘에 대한 설명은 다음 블로그 링크를 참조해주세요. 문제는 크게 두 부분으로 나뉘어 집니다. 1. 바다를 제외한 연결된 영역을 같은 섬 영역으로 표시하고 각 섬마다 구분 지어 주기 2. 각 섬에서 다른 섬까지 이어지는 경로 찾기 1번의 경우 일반적인 ..

※ https://rh-tn.tistory.com/ 와 동시에 업로드 됩니다. 목차 1. Prim 알고리즘의 개념 2. Prim 알고리즘의 구현 3. Kruskal 알고리즘과 Prim 알고리즘의 비교 이전 포스팅에서는 최소 신장 트리를 만들기 위한 알고리즘으로 Kruskal 알고리즘에 대하여 알아보았습니다. 이번 포스팅에서는 최소 신장 트리를 구현하는 또 다른 알고리즘인 Prim 알고리즘에 대해 알아보도록 하겠습니다. Prim 알고리즘은 Union-Find 와 같은 알고리즘을 몰라도 구현할 수 있습니다. 하지만 구현이 Kruskal 알고리즘에 비해 복잡합니다. 개념 Prim 알고리즘은 다음과 같은 방법으로 동작을 수행합니다. 임의의 정점을 선택하여 최소 신장 트리에 추가합니다. 최소 신장 트리에 포함된 ..

※ https://rh-tn.tistory.com/ 와 동시에 업로드 됩니다. 목차 1. 최소 신장 트리의 정의 2. Kruskal 알고리즘의 개념 3. Kruskal 알고리즘 구현 정의 최소 신장 트리 (Minimum Spanning Tree)에 대해 알아보기 전에 우선 신장 트리가 무엇인지 알아보겠습니다. 신장 트리(Spanning Tree)는 무방향 연결 그래프가 존재할 때, 그 그래프에서 모든 정점을 포함하도록 간선을 부분적으로 선택하여 만들 수 있는 부분 그래프 입니다. 어떤 그래프가 정점 V개와 E개의 간선을 가지고 있다고 가정하면 신장 트리의 정점과 간선의 개수는 각각 V와 V-1이 되겠습니다. 최소 신장 트리는 그 중에서도 가중치가 있는 그래프일 때를 고려합니다. 그래프의 간선마다 가중치가..