알고리즘(Java)/Recursive & Tree & Graph13 [알고리즘]Graph - 그래프 최단거리(BFS) 그래프에서 1번 정점에서 각 정점으로 가는 최소 이동 간선수를 출력하는 프로그램 import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int n, m, answer = 0; static int[] ch, dis; static ArrayList graph; public static void BFS(int v) { Queue queue = new LinkedList(); ch[v] = 1; dis[v] = 0; // 1에서 1까지 거리는 0 queue.offer(v); while (!queue.isEmpty()) { int .. 2021. 8. 30. [알고리즘]Graph - 경로 탐색(인접리스트, DFS) 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램 import java.util.ArrayList; import java.util.Scanner; public class Main { // DFS static int n, m, answer = 0; static int[] ch; static ArrayList graph; public static void DFS(int v) { if (v==n) answer++; else { for (int nv : graph.get(v)) { // 인접리스트 탐색 -> for each가 편함 if (ch[nv]==0) { ch[nv] = 1; DFS(nv); ch[nv] = 0; } } } } public static void.. 2021. 8. 30. [알고리즘]Graph - 경로 탐색(인접행렬, DFS) Graph(그래프) - G(V, E) Vertex(정점), Edge(간선)으로 구성되어있다. 종류 Adjacency Matrix(인접행렬) 인접 정점을 찾기 위해 모든 정점을 순회해야 한다. 그래프에 간선이 많이 존재하는 밀집 그래프인 경우 유리하다. Adjacency List(인접리스트) 정점의 개수가 많은 경우 유리하다. 그래프에 간선이 적게 존재하는 희소 그래프인 경우 유리하다. 그래프 탐색 DFS: 깊이 우선 탐색 -> stack BFS: 너비 우선 탐색 -> queue 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램 import java.util.Scanner; public class Main { // DFS static int n, m, answ.. 2021. 8. 30. [알고리즘]BFS - Tree 말단 노드까지의 가장 짧은 경로 아래 그림과 같은 이진트리에서 루트 노드 1에서 말단노드까지의 길이 중 가장 짧은 길이를 구하는 프로그램 import java.util.LinkedList; import java.util.Queue; class Node { int data; Node lt, rt; public Node(int val) { data = val; lt = rt = null; } } public class Main { Node root; public int BFS(Node root) { Queue queue = new LinkedList(); queue.offer(root); int level = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int i=0; i 2021. 8. 30. [알고리즘]DFS - Tree 말단 노드까지의 가장 짧은 경로 아래 그림과 같은 이진트리에서 루트 노드 1에서 말단노드까지의 길이 중 가장 짧은 길이를 구하는 프로그램 class Node { int data; Node lt, rt; public Node(int val) { this.data = val; this.lt = this.rt = null; } } public class Main { Node root; public int DFS(int level, Node root) { if (root.lt==null && root.rt==null) return level; else return Math.min(DFS(level+1, root.lt), DFS(level+1, root.rt)); } public static void main(String[] args) { Ma.. 2021. 8. 29. [알고리즘]BFS - 송아지 찾기 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램 현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아 지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음 과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. * 첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000까지이다. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Mai.. 2021. 8. 27. 이전 1 2 3 다음
