[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]);
    }
}