반응형
문제
https://www.acmicpc.net/problem/2644
2644번: 촌수계산
사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어
www.acmicpc.net
풀이
- 예제입력 1를 트리로 그려보았음
- 7 -> 3의 촌수는 3임, (3만큼의 거리로 해석하였습니다)
- 촌수를 계산해야 하는 번호 중 앞번호를 Start, 도착 번호를 End로 두고, DFS/BFS를 Start 번호부터 시작 한 후, 도착 번호를 만난다면 그때의 Depth를 출력해주면 되겠다고 생각했다.
- 만약 도달할 수 없다면 -1 을 출력해주자!
소스코드
후기
그래프의 간선의 비용이 1인 상황에서 최단 거리를 구하는 문제였던 것 같다.
간선의 비용이 1일 때, 최단 거리를 구하는 문제는 BFS를 사용해서 풀었던 것 같은데 이번 문제는 순환하지 않는 무방향 그래프이기 때문에 DFS로도 풀이가 가능했던 것 같다.
어렵지 않게 풀 수 있었던 문제였다.
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 11725 트리의 부모 찾기 (Swift) (0) | 2022.11.11 |
|---|---|
| [BOJ] 백준 11724 연결 요소의 개수 (Swift) (0) | 2022.11.11 |
| [BOJ] 백준 4963 섬의 개수 (Swift) (0) | 2022.11.10 |
| [BOJ] 백준 1012 유기농 배추 (Swift) (0) | 2022.11.08 |
| [BOJ] 백준 2606 바이러스 (Swift) (0) | 2022.11.07 |
