Java構文とアルゴリズム(BFS)
BFSとは?
最短距離を探すアルゴリズム
進行方法
建造
LEVEL 0 : 1
LEVEL 1 : 2 -> 3
LEVEL 2:4->5->6->7が回転し、接続がなくなりましたので、キューを終了します.
コード#コード#
package inflearn.section7_bfs;
import java.util.*;
class Node {
Node lt,rt;
int data;
Node(int value) {
data=value;
lt=rt=null;
}
}
public class Main1 {
Node root;
public void bfs(Node root) {
Queue<Node>queue=new LinkedList<>();
// 값을 넣는다
queue.add(root);
int level=0;
while (!queue.isEmpty()) {
System.out.print(level+" : ");
// 큐에서 한개 뽑는다.
// Node node=queue.poll();
// 뽑은거 출력
int size=queue.size();
for (int i=0;i<size;i++) { // 여기서 주의! 큐에 들어가면서 큐 사이즈가 변하기 때문에 미리 큐 사이즈를 변수(size)에 저장한다.
// System.out.println("queue_size"+queue.size());
Node node=queue.poll();
System.out.print(node.data+" ");
// 왼쪽 오른쪽 넣기
if (node.lt!=null) queue.add(node.lt);
if (node.rt!=null) queue.add(node.rt);
}
System.out.println();
level++;
}
}
public static void main(String[] args) {
Main1 main=new Main1();
// Node 생성
main.root=new Node(1);
main.root.lt=new Node(2);
main.root.rt=new Node(3);
main.root.lt.lt=new Node(4);
main.root.lt.rt=new Node(5);
main.root.rt.lt=new Node(6);
main.root.rt.rt=new Node(7);
// 이거 넣을때 주위, main.root를 넣어야 함
main.bfs(main.root);
}
}
に質問子牛をさがす
解決策
package inflearn.section7_bfs;
// 송아지 찾기 문제 BFS - 레벨 별 탐색
import java.util.*;
public class Main2 {
// 전역변수
static int n;
static int m;
int arr[]=new int[10001];
int dx[]={-1,1,5};
public int solution(int n) {
Queue<Integer> queue=new LinkedList<>();
int level=0;
queue.add(n);
// 처음 방문 -> 1로 처리 (방문 처리)
arr[n]=1;
while (!queue.isEmpty()) {
int size=queue.size();
for (int i=0;i<size;i++) {
int k=queue.poll();
// arr[k]=1; // 처음 갑
if (k==m) {
return level;
}
else {
for (int j=0;j<dx.length;j++) {
int nx=k+dx[j];
// 큐에 넣기
if (nx>=1 && nx<=10000 && arr[nx]==0) { // 방문하지 않았으면
arr[nx]=1; // 넣고 방문 처리
queue.add(nx);
}
}
}
}
level++;
}
int answer=0;
return answer;
}
public static void main(String[] args) {
Main2 main=new Main2();
Scanner scan=new Scanner(System.in);
n=scan.nextInt();
m=scan.nextInt();
System.out.println(main.solution(n));
}
}
ツリー末端ノードへの最短パス
コード#コード#
package inflearn.section7_bfs;
import java.util.*;
class Node4 {
Node4 lt;
Node4 rt;
int val=0;
Node4(int val) {
lt=rt=null;
this.val=val;
}
}
public class Main4 {
Node4 node4;
public int bfs(int l,Node4 node4) {
Queue<Node4> queue=new LinkedList<>();
queue.add(node4);
while(!queue.isEmpty()) {
int size=queue.size();
for (int i=0;i<size;i++) {
Node4 node=queue.poll();
// 말단 노드
if (node.lt==null && node.rt==null) {
return l;
}
queue.add(node4.lt);
queue.add(node4.rt);
}
l++;
}
return 1;
}
public static void main(String[] args) {
Main4 main4 =new Main4();
main4.node4=new Node4(1);
main4.node4.lt=new Node4(2);
main4.node4.rt=new Node4(3);
main4.node4.lt.lt=new Node4(4);
main4.node4.lt.rt=new Node4(5);
int l=0;
System.out.println(main4.bfs(l,main4.node4));
}
}
Reference
この問題について(Java構文とアルゴリズム(BFS)), 我々は、より多くの情報をここで見つけました https://velog.io/@sds1vrk/자바-문법-및-알고리즘-BFSテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol