문제
출처 : https://www.acmicpc.net/problem/2644
2644번: 촌수계산
사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진
www.acmicpc.net
입력받은 두 사람의 촌수를 계산하는 문제다.
풀이
매우 기초적인 그래프 문제다.
연결거리가 1 늘어날수록 촌수또한 1 늘어난다.
깊이우선탐색으로 입력받은 사람의 촌수를 계산해주면된다.
(이때, 자손은 항상 한명의 부모만 가질수있으므로, 이 그래프는 항상 트리구조이다.)
소스코드
https://github.com/devxb/JJUNalgo/blob/master/2644%20%EC%B4%8C%EC%88%98%EA%B3%84%EC%82%B0/Main.java
devxb/JJUNalgo
백준 알고리즘 소스코드🙃. Contribute to devxb/JJUNalgo development by creating an account on GitHub.
github.com
'알고리즘 (2020 : 08 : 10 ~ ) > BFS,DFS' 카테고리의 다른 글
| [백준 / BOJ] 5827 What's Up With Gravity (0) | 2021.05.14 |
|---|---|
| [백준 / BOJ] 14466 소가 길을 건너간 이유 6 (Java) (0) | 2021.05.12 |
| [백준 / BOJ] 1039 교환 (0) | 2021.04.20 |
| [백준 / BOJ] 14502 연구소 (0) | 2021.01.21 |
| [백준 / BOJ] 16953 A -> B (0) | 2021.01.17 |