알고리즘3 [Algorithm] MST (최소 신장 트리) 프림(Prim) MST(Minimum Spanning Tree 최소 신장 트리) 프림 알고리즘(Prim's algorithm)가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용을 찾는 알고리즘이다. (greedy algorithm 임) 개요프림 알고리즘은 아래의 순서대로 작동한다: 그래프에서 임의의 하나의 정점을 선택한다.선택한 정점과 인접하는 정점들중 최소 비용의 간선이 존재하게되는 정점을 선택한다.1.2 과정을 반복 하여 모든 정점이 선택될까지 한다. 알고리즘이 종료됐을 때 만들어진 트리는 최소 비용 신장트리가 된다. 동작 예제 어떤 점에서 시작하던 관계는 없습니다. 좌측 그래프에서는 임의의 시작점 D를 선택합니다. D지점.. 2017. 7. 7. [Java] 백준9663 N-Queen https://www.acmicpc.net/problem/9663 가로세로대각선으로 움직일 수 있는 막강한 말인 Queen을 서로 공격할 수 없는 위치에 놓는 경우의 수를 구하는 문제. 한줄에 하나의 Queen밖에 못 놓으므로 맵을 다 선언해주지 않아도 됨.N크기의 배열을 선언한 후 재귀로 경우의 수를 구한다.조건 1. 같은 열에 있거나조건 2. 대각선에 위치할 경우를 제외하고 찾는다. import java.util.Scanner;public class Problem9663_NQueen {static int path[] = new int[16];static int n;static int ans;public static void main(String[] args) {Scanner sc = new Scann.. 2017. 5. 21. [Java] 백준 1260 DFS BFS DFS (Depth First Search) 깊이 우선 탐색인접해 있는 점 순으로 탐색해 나감 ( 재귀 사용 ) BFS (Breadth First Search) 너비 우선 탐색가까운 정점 먼저 탐색 후 점차 한단계씩 탐색해 나감 문제 1260https://www.acmicpc.net/problem/1260 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. DFS BFS 를 동시에 구현했습니다. 12345678910111213141516171819202122232425262728293031323334353637383940414243.. 2017. 4. 7. 이전 1 다음