문제 : 촌수계산

문제링크
실버 2
그래프 탐색

부모- 자식 => 1촌
주어진 두사람의 촌수를 구하시오

입력

전체 사람의 수 n (사람이 1~n으로 주어짐)
촌수를 계산해야하는 두사람의 번호
부모 자식간의 관계 갯수 m
부모 자식의 관계를 나타내는 번호 x,y(x가 y의 부모)

출력

촌수를 정수로 출력
친척이 아닐때 -1 출력

풀이

1. bfs를 통해 목적지에 도착할때까지의 depth를 찾는다.

코드

import java.util.*;

public class 백준2644 {
	static int n,p1,p2,m,cnt=0;
	static Scanner scan =new Scanner(System.in);
	static ArrayList<ArrayList<Integer>> list=new ArrayList<>();
	
	static int[] visited;
	static StringBuilder sb=new StringBuilder();

	public static void main(String[] args) {
		// 입력
		n=scan.nextInt();//전체 사람의수
		p1=scan.nextInt();// 촌수 계산 하려는 사람1
		p2=scan.nextInt();// 촌수 계산 하려는 사람2
		m=scan.nextInt();// 부모자식 관계 m
		visited=new int[n+1];
		for(int i=0;i<n+1;i++) {
			list.add(new ArrayList<Integer>());
		}
		for(int i=0;i<m;i++) {
			int a=scan.nextInt();
			int b=scan.nextInt();
			list.get(a).add(b);
			list.get(b).add(a);
		}
		
		bfs();
		
		System.out.print(visited[p2]-1);
	}
	static void bfs() {
		Queue<Integer> q=new LinkedList<>();
		
		q.offer(p1);
		visited[p1]=1;
		int next=0;
		while(!q.isEmpty()) {
			
			next=q.poll();
			int size=list.get(next).size();
			for(int i=0;i<size;i++) {
				int a=list.get(next).get(i);
				if(visited[a]==0) {
					visited[a]=visited[next]+1;
					q.offer(a);
				}
			}
			
		
		}
	}

}