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

풀이

• 상하좌우 조사
• 현재 위치를 상하좌우 조사한 위치에서 올 수 있는지 확인
• 재귀
• 계속 d 배열이 채워지질 않는다..

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

풀이

• bj_1167 과 동일한 문제
• 1을 루트로 지정하고 가장 먼 위치에 있는 정점 찾고
• 그 정점에서 모든 정점들 사이의 거리 찾아서
• 가장 큰게 답

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

풀이

• bfs로 탐색
• 루트에서 모든 정점까리 거리 구함
• 가장 먼 거리 정점 : A
• A는 이제 루트
• 모든 정점까지 거리 구함
• 가장 먼 거리가 지름

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

풀이

• 매우 쉬운 문제
• Person class 생성
• 입력 값에 따라 Person에 저장
• 정렬

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