트리의 부모 찾기

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

Comments