[DFS BFS]-2644カウント
リンクテキスト
カウント
カウント
私と父は一寸です.
おじいさんとお父さんは一寸の関係です.
私とおじいさんは二寸の関係です.
ラフデザイン
国の頂点がお父さんまでの頂点なら、片足のお父さんからおじいさんまでの頂点は両足です。
郷愁関係を定義した。頂点を通るたびにcountで設計すればいいと思っています。
隣接リストを使用して頂点を参照します.寸法が定義されていない場合は注意してください.ループをtrueに設定してbreakを待つと、無限ループに陥る可能性があります.したがって、すべての検索(完全検索)後に、配列間の寸法関係を定義し、インデックスとして入力する配列を作成することが望ましい.package oneDay_twoSol.DB_FirstSearch;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class degrees_Relationship {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int count[]=new int[n+1];
ArrayList<ArrayList<Integer>> degreeRelationship=new ArrayList<>();
for (int i = 0; i <= n; i++) {
degreeRelationship.add(new ArrayList<>());
count[i]=-1;
}
int solvingCount=sc.nextInt();
int solvingCount2=sc.nextInt();
int m=sc.nextInt();
// adjList
for (int i = 0; i < m; i++) {
int a=sc.nextInt();
int b=sc.nextInt();
// 무방향 그래프 특징.
degreeRelationship.get(a).add(b);
degreeRelationship.get(b).add(a);
}
count[solvingCount]=0;
Queue<Integer> q =new LinkedList<>();
q.offer(solvingCount);
while (!q.isEmpty())
{
int current=q.poll();
for (int i = 0; i < degreeRelationship.get(current).size(); i++) {
int next=degreeRelationship.get(current).get(i);
if(count[next]==-1)
{
count[next]=count[current]+1;
q.offer(next);
}
}
}
System.out.println(count[solvingCount2]);
}
}
Reference
この問題について([DFS BFS]-2644カウント), 我々は、より多くの情報をここで見つけました
https://velog.io/@admin1194/DFSBFS-2644촌수계산
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
package oneDay_twoSol.DB_FirstSearch;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class degrees_Relationship {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int count[]=new int[n+1];
ArrayList<ArrayList<Integer>> degreeRelationship=new ArrayList<>();
for (int i = 0; i <= n; i++) {
degreeRelationship.add(new ArrayList<>());
count[i]=-1;
}
int solvingCount=sc.nextInt();
int solvingCount2=sc.nextInt();
int m=sc.nextInt();
// adjList
for (int i = 0; i < m; i++) {
int a=sc.nextInt();
int b=sc.nextInt();
// 무방향 그래프 특징.
degreeRelationship.get(a).add(b);
degreeRelationship.get(b).add(a);
}
count[solvingCount]=0;
Queue<Integer> q =new LinkedList<>();
q.offer(solvingCount);
while (!q.isEmpty())
{
int current=q.poll();
for (int i = 0; i < degreeRelationship.get(current).size(); i++) {
int next=degreeRelationship.get(current).get(i);
if(count[next]==-1)
{
count[next]=count[current]+1;
q.offer(next);
}
}
}
System.out.println(count[solvingCount2]);
}
}
Reference
この問題について([DFS BFS]-2644カウント), 我々は、より多くの情報をここで見つけました https://velog.io/@admin1194/DFSBFS-2644촌수계산テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol