친척 간의 거리

지침

여러분의 과제는 가계도에서 두 사람 사이의 분리 정도를 구하는 거예요. 이것은 모든 할리우드 배우가 케빈 베이컨과 6단계 이내로 연결되어 있다는 대중문화 속 이야기와 비슷해요.

• 부모의 이름과 그 자녀들이 담긴 입력이 주어져요.
• 이름은 모두 고유하고, 자녀에게는 부모가 한 명 또는 두 명일 수도 있어요.
• 분리 정도는 한 사람에서 다른 사람까지 이어지는 가장 짧은 연결 수로 정의해요.
• 두 사람이 연결되어 있지 않다면, "알려진 관계 없음"을 나타내는 값을 반환해요. 실제 구현은 테스트 케이스를 참고해요.

예시

다음과 같은 가계도가 주어졌다고 해봐요:

      ┌──────────┐            ┌──────────┐     ┌───────────┐
      │  Helena  │            │  Erdős   ├─────┤  Shusaku  │
      └───┬───┬──┘            └─────┬────┘     └────┬──────┘
      ┌───┘   └───────┐             └───────┬───────┘
┌─────┴────┐     ┌────┴───┐           ┌─────┴────┐
│   Isla   ├─────┤ Tariq  │           │   Kevin  │
└────┬─────┘     └────┬───┘           └──────────┘
     │                │
┌────┴────┐      ┌────┴───┐
│   Uma   │      │ Morphy │
└─────────┘      └────────┘

Tariq와 Uma의 분리 정도는 2예요 (Tariq → Isla → Uma). Isla와 Kevin 사이에는 알려진 관계가 없어요. 주어진 데이터에 연결이 없기 때문이에요. Uma와 Isla의 분리 정도는 1이에요.

---

출처

vaeng