트리의 부모 찾기

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

틀린 풀이

• int a[][]= new int[n][3]

  • 왼쪽 자식, 오른쪽 자식, 부모를 저장 할 배열 생성

• 전위 순회

  • 트리에서 입력한 line의 첫 번째 수가 있는지 탐색

• 찾았으면 왼쪽 자식이, 오른쪽 자식이 비었는지 확인

• 못 찾았으면 입력한 line의 두번째 수가

  • 왼쪽 자식 비었는지, 오른쪽 자식 비었는지 확인

• 이게 과연 효과적인 방법일까 ?

옳은 풀이

• “도시가 n개 + 도로가 n-1개 + 두 도시 사이에 경로가 항상 존재 + 방향 X ==> 트리임”

• 트리의 탐색 : BFS / DFS 로 가능

• 트리는 사이클이 없는 그래프

• 따라서, 두 정점 사이 경로는 1개

• now -> next로 가려면

  • 간선이 있어야함
  • next를 아직 방문하지 않았어야함 => check[next] == false

• 알게 되는 것

  • parent[next] = now
  • depth[next] = depth[now] +1