[백준] 2644 촌수계산 (BFS)

남혁준 2020. 1. 16. 17:03

https://www.acmicpc.net/problem/2644

2644번: 촌수계산

사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다. 각 사람의 부모는 최대

www.acmicpc.net

BFS를 사용해 촌수를 계산하는 문제입니다.

각 사람의 정보와 촌수를 저장하는 클래스를 만들어 사용했습니다.

시작을 x, 촌수 0으로 시작해서 연결된 사람이 있으면 현재촌수 + 1 해주며 큐에 담습니다.

BFS진행 중 y차례가 되면 촌수를 저장하고 BFS를 종료합니다.