문제 설명
무성 생식을 하는 단세포 생물의 계통도와 두 개체의 이름을 입력받아 두 개체의 유전 거리를 구하는 프로그램을 작성하시오. 단 입력되는 최대 개체 수는 알파벳 개수를 넘지 않는다.
유전 거리는 개체 간 유전적 유사도를 나타내는 것으로 다음과 같이 두 개체 간 이동 시 거치게 되는 개체 수로 정의된다.
개체 A와 개체 G의 유전 거리는 A-B-E-G의 순서대로 이동한다. B-E-G의 새 개체를 거치므로 거리는 3이고, 개체 D와 E의 유전 거리는 D-B-E로 두 개체를 거쳐야 하므로 거리는 2이다.
유전 거리는 개체 간 유전적 유사도를 나타내는 것으로 다음과 같이 두 개체 간 이동 시 거치게 되는 개체 수로 정의된다.
개체 A와 개체 G의 유전 거리는 A-B-E-G의 순서대로 이동한다. B-E-G의 새 개체를 거치므로 거리는 3이고, 개체 D와 E의 유전 거리는 D-B-E로 두 개체를 거쳐야 하므로 거리는 2이다.
입력 설명
첫 번째 줄에 트리를 리스트로 표현한 문자열 한 줄이 입력된다.
루트 노드의 인덱스는 \(1\)이며, \(i\)노드의 왼쪽 자식의 인덱스는 \(2*i\)이며 오른쪽 자식의 인덱스는 \(2*i+1\)이다.
두 번째 줄에 두 개체의 이름(알파벳)이 공백으로 구분되어 입력된다.
두 번째 줄에 두 개체의 이름(알파벳)이 공백으로 구분되어 입력된다.
출력 설명
유전거리를 출력한다.
입력 예시 Copy
-ABCDE----FG----
D E
출력 예시 Copy
2