링크텍스트

촌수계산

나와 아버지는 1촌
할아버지와 아버지는 1촌 관계

나와 할아버지는 2촌 관계

대략 설계
나 라는 정점을 아빠 까지의 정점으로 가는 경우 1다리 아빠에서 할아버지 정점까지 가는데 2다리
라고 생각하는 촌수 관계를 정의 하였다. 정점을 지날 때마다 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]);
    }
}