dfs. [2644]

[1. 문제 설명]

https://www.acmicpc.net/problem/2644

---

[2. 풀이 접근]

그래프 구축

• 모든 부모 자식 간의 관계에 대해서, 그래프를 무방향 그래프로 구축해야 한다.
• 부모->자식으로 가는 방향 그래프로 구축한다면, 임의의 두 사람 u, v 에 대해서 촌수를 구할 수 없다.
• u 가 자식이고, v 가 부모인 경우, u->v 인 edge 는 존재하지 않기 때문이다.
• 따라서, 그래프는 무방향 그래프로 구축해야 한다. 

DFS 종료 시 처리

• u 에서 dfs 를 시작하였는데, v 를 만나지 못했다면, 
• 재귀를 종료하고 되돌아가는 시점에서, 현재까지 방문한 모든 정점에 대해서
• 다시 미방문 처리하지 않아도 된다.
• 이 정점들은 v 와는 아무 관련이 없기 때문이다.
• u 에서 dfs 시작 후, a, b, c 를 방문했다면, 이 정점들은 u 와 v 의 촌수를 구하는데 아무 영향이 없다.

---

[3. 코드]