난이도 : 골드 5 걸린 시간 : 30분 문제 보물섬 문제 바로가기 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다. 예를 들어 위와 같이 지도가 주어졌다면 보물은 아래 표시된 두 곳에 묻혀 있게 되고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다. 보물..

최단 경로 그래프에서 유도되는 문제들 중 최단 경로 문제가 있다. 주어진 그래프에서 특정 정점에서 다른 정점까지의 최단 경로(가중치 합이 최소인 경로)가 무엇인지를 알아내는 문제이다. 이는 이전의 MST 문제와 다르다. 모든 정점을 포함할 필요가 없기 때문이다. 하지만 MST에서 사용했던 Prim(Dijkstra) 알고리즘을 응용해서 구현할 수 있다. [MST] Dijkstra 알고리즘 구현 vertice(정점)는 3가지 분류로 나뉜다. tree vertice(T) : tree에 속해 있는 정점 fringe vertice (F) : tree에 포함되지 않으면서 연결되어있는 정점 unseen vertice (U) : 나머지 MST에서 T와 F의 정점 사이의 최소 가중치를 계속 갱신해주었던 것 대신에, 최단..

MST Spanning Tree : 그래프 내의 모든 정점을 포함하는 트리 우선 트리의 정의는 connected undirected acyclic graph (연결 비방향 비순환 그래프)이다. 모든 노드는 연결되어있으며, 방향성은 없고 순환이 존재하지 않는 그래프이다. 하나의 그래프가 주어졌을 때, 그래프 내에서 여러 트리를 찾을 수 있다. 그 중 특별하게 모든 정점을 포함하는 트리를 Spanning Tree라고 한다. 다르게 말하면 Spanning tree(신장 트리)는 그래프의 부분 그래프면서 간선의 수가 가장 적은(최소 연결) 그래프이다. 감이 안온다면 그림으로 살펴보자. 위의 그림과 같이 그래프가 주어졌을 때, 최소한의 간선을 사용하여 모든 정점을 포함하는 부분 그래프가 여러 개 존재한다. 이 부..