알고리즘
1. BFS를 할 때마다 특정 번호의 촌수를 계산하기 위해서 Node 클래스를 선언한다.
2. 먼저 주어지는 사람의 번호를 src, 나중에 주어지는 번호를 dsc라고 정의한다.
3. 주어진 값들을 입력받을 때 아직 촌수를 알 수 없기 때문에 각 번호에 대한 촌수를 0으로 초기화한다.
4. BFS로 dst를 찾을 때까지 각각의 Node를 탐색하면서 cur.degree를 1씩 더하는 방식으로 번호들의 촌수를 초기화한다.
5. 큐에서 꺼낸 Node의 번호가 dst와 같으면 cur.degree를 반환한다.
6. 만약에 모든 Node를 탐색할 때까지 dst를 찾지 못하면 -1을 반환한다.
소스코드
문제링크
2644번: 촌수계산
사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어
www.acmicpc.net
'Coding Test > Solved' 카테고리의 다른 글
| [BOJ] 백준 18405번 - 경쟁적 전염(with Java) (0) | 2022.06.28 |
|---|---|
| [BOJ] 백준 1697번 - 숨바꼭질(with Java) (0) | 2022.06.28 |
| [BOJ] 백준 1260번 - DFS와 BFS(with Java) (0) | 2022.06.26 |
| [프로그래머스] Level 1 - 신고 결과 받기(with Java) (0) | 2022.03.22 |
| [BOJ] 백준 16637번 - 괄호 추가하기(with Java) (0) | 2022.01.05 |
댓글