문제 이해

부모와 자식 사이를 1촌으로 정의한다.
만약 부모와 A라는 사람이 x촌 관계라면, 자식(B)과 A라는 사람은 (x+1)촌 관계가 된다.
(A = B가 아니라면)

이 때 주어진 두 사람의 촌수를 계산하여 출력하는 문제이다.

---

문제 풀이

말이 어렵지만, 결국은 두 개의 점이 몇 개의 간선을 통해 서로 이어져 있냐고 물어보는 문제이다.
"부모"와 "자식" 관계라는 말이 있어 방향 그래프로 생각할 수도 있지만, 각 사람의 부모는 최대 한명만 주어진다고 쓰여있다. 즉, A ⇒ B ⇒ C로 갈 때, B가 A와 C의 자식인 경우는 절대 존재할 수 없다는 의미이다. 이 말인 즉슨, B는 A와 C의 부모라는 의미이며, 자연스럽게 A와 C는 1 + 1 = 2촌 사이라는 것을 알 수 있다.

가중치 없는 무방향 그래프에서의 최단 거리를 찾는 문제이다.

따라서 BFS를 통해 문제를 해결하였다.

---

코드

import java.io.*;
import java.util.*;

class Family{
	int parent;
	int count;
	
	public Family(int from, int count) {
		this.parent = from;
		this.count = count;
	} 
}

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int n;
	static int from, to;
	static ArrayList<Integer>[] parents;
	static boolean[] visit;
	
	static Integer bfs() {
		
		Queue<Family> queue = new LinkedList<>();
		
		queue.add(new Family(from, 0));
		
		while(!queue.isEmpty()) {
			Family tmp = queue.poll();
			
			if(tmp.parent==to) return tmp.count; 
            // 최단 거리에 대한 DFS 특징
            
			if(visit[tmp.parent]) continue; 
            // 이미 방문했던 점은 중복 처리할 필요가 없으므로 생략
			
			visit[tmp.parent] = true; // 방문 처리
			for(int s:parents[tmp.parent]) {
				queue.add(new Family(s, tmp.count+1));
			}
		}
		
		return -1;
        // 만약 return tmp.count가 수행되지 않았다면 이 부분까지 수행될 것이다.
        // 이 말인 즉슨, A -> B로 가는 Route가 없다는 의미이므로, 
        // 촌수를 계산할 수 없다는 의미이다.
	}
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();

		n = sc.nextInt();
		from = sc.nextInt();
		to = sc.nextInt();
		
		parents = new ArrayList[n+1];
		visit = new boolean[n+1];
		
		for(int i =1;i<n+1;i++) {
			parents[i] = new ArrayList<>();
		}
		
		int size = sc.nextInt();
		
		for(int i =0;i<size;i++) {
			int tmp1 = sc.nextInt();
			int tmp2 = sc.nextInt();
			
			parents[tmp1].add(tmp2);
			parents[tmp2].add(tmp1);
		}
		
		System.out.println(bfs());
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과