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