2644 – 촌수계산
2644번: 마을 수 계산 문제 한국은 가족 또는 친척 간의 관계를 마을 수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자녀 사이를 1촌으로 정의하고, 앞으로 사람들 사이의 마을 수를 계산한다. 예를 들어 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나가고, 할아버지는 2촌이 되고, 아버지 형제와 할아버지는 1촌, 나와 아버지 형제와는 3촌이 된다. 여러 사람에 대한 부모-자녀 관계가 주어졌을 때 주어진 두 사람의 마을 수를 계산하는 프로그램을 만들어라. 입력은 1,2····www.acmicpc.net
문제.
인기글
해석, 해, 풀 것.
해석, 해, 풀 것.
깊이 우선 탐색과 폭 우선 탐색의 두 가지 방법으로 풀 수 있는 문제였습니다. 풀이에서는 두 가지 방법을 사용해서 풀었어요. 마을 수를 노드로 취급하고 1촌간은 간선으로 연결한다고 생각해서 풀었습니다. graph에는 1촌끼리 연결해서 만든 노드그래프가 저장되게 됩니다. 이를 바탕으로 그래프 탐색을 통해 문제를 풀었습니다. DFS 또는 BFS 탐색을 하여 목표 노드에 도달하지 못할 경우 -1을 출력하고 목표 노드에 도달할 경우에는 도달할 때까지 카운트 해준 d를 출력합니다. 알고리즘 종류 – 그래프 이론 – 그래프 탐색 – 폭 우선 탐색 – 깊이 우선 탐색