트리3 [백준] 1991번, 트리 순회 | (python,파이썬) 문제 링크 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 문제 문제해결하기 ○ 트리의 순회 ? 트리의 순회는 세가지 방법으로 preorder, inorder, postorder가 있다. (M의 위치 기준으로 이름을 지었다.) ▷Preorder: M L R (Middle 노드 출력 → Left subtree 순회 → Right subtree 순회) ▷Inorder: L M R (Left subtree 순회 → Middle 노드 출력 → Right subtree 순회) ▷Postorder: L R M (L.. 2021. 7. 28. [백준] 1167번, 트리의 지름 | (python,파이썬) 문제 링크 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 문제해결하기 트리의 지름 ? 트리의 지름이란 가장 먼 두 정점 사이의 거리, 연결하는 경로를 의미한다. 쉽게 얘기하면, 트리 내의 임의의 두 정점사이의 거리가 가장 길때, 그 길이가 트리의 지름이다. 그러면 트리의 지름은 어떻게 구할까 ? i. 트리에서 임의의 정점을 정한다 ii. 위에서 택한 임의의 점 하나에서 가장 거리가 먼 정점 a를 찾는다. iii. 정점 a에서 가장 거리가 먼 정점, 그 길이가 트리의 지름이다. ○간선의 .. 2021. 7. 28. [백준] 11725번, 트리의 부모 찾기 | (python,파이썬) 문제 링크 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 문제해결하기 노드를 생성하여 트리를 구성하는데에 익숙한지라 하나하나 노드를 생성하여 트리를 만들려고 했지만, 노드 당 자식을 설정하는 것이 쉽지않아 실패했다. 그래서 자식노드를 큰 제한없이 설정 가능한 그래프로 접근하기로 했다 ! DFS로 그래프를 순회하면서 부모의 정보를 업데이트 해주었다. 정답코드 import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline def DFS(G, v): visited_D[v] = True for w in G[v] : i.. 2021. 7. 23. 이전 1 다음
