본문 바로가기

트리

 (14)
백준 1717 집합의 표현 - 파이썬 문제. 풀이. 유니온 파인드의 이해가 필요하다. 유니온 파인드는 순수히 노드 간의 연결 관계를 파악할 때 유용하게 사용된다. 유니온 파인드에는 유니온 연산과 파인드 연산이 있다 1) Union -> 서로 다른 두 트리(집합)을 합치는 연산 2) Find -> 루트 노드를 찾는 연산 find 연산은 어떤 노드를 인자로 넘겼을 때, 해당 노드의 루트 노드를 반환하며 재귀 호출의 형태로 구현한다. 시간 복잡도 효율을 높이기 위하여 자식 노드들의 값을 모두 루트 노드를 변경하여 경로 압축 최적화를 진행한다. union 연산은 서로 다른 두 트리(집합)을 합친다. 각 트리의 루트 노드를 비교하여 둘 중 작은 루트 노드를 기준으로 합치게 된다. 소스코드.
백준 2263 트리의 순회 - 파이썬 풀이. 다음과 같은 트리가 있다하면 순회의 결과는 다음과 같다. 전위 순회 : 0->1->3->7->8->4->9->10->2->5->11->6 중위 순회 : 7->3->8->1->9->4->10->0->11->5->2->6 후위 순회 : 7->8->3->9->10->4->1->11->5->6->2->0 중위와 후위를 살펴보면, 후위의 마지막 요소가 루트 노드인 것을 알 수 있다. 그러면 중위 순회에서 루트 노드를 기준으로 left, right를 나누면 (7, 3, 8, 1, 9, 4, 10), (11, 5, 2 6)으로 나뉘어진다. 이 left, right의 길이만큼 후위 순회에서 나눈다면 (7, 8, 3, 9, 10, 4 ,1), (11, 5, 6, 2) 로 나뉘어진다 다시 후위 순회와 중위 순회를 ..
백준 1991 트리의 순회 - 파이썬 문제. 풀이. 트리의 순회만 안다면 매우 쉽게 풀 수 있다. 전위 순회 = 루트, 왼쪽 , 오른쪽 중위 순회 = 왼쪽, 루트, 오른쪽 후위 순회 = 왼쪽, 오른쪽, 루트 이다. 딕셔너리를 이용하여 풀었다. import sys # 전위순회 def preorder(root): if root !='.': print(root, end='') preorder(tree[root][0]) preorder(tree[root][1]) # 중위순회 def inorder(root): if root !='.': inorder(tree[root][0]) print(root, end='') inorder(tree[root][1]) # 후위순회 def postorder(root): if root !='.': postorder(tr..
백준 1967 트리의 지름 - 파이썬 문제. 풀이. https://turret1234.tistory.com/171 백준 1167 트리의 지름 - 파이썬 문제. 풀이. BFS를 이용하여 1번 노드와 가장 거리가 먼 노드를 구한다. 그리고나서 그 노드와 가장 거리가 먼 노드를 구하고 그 거리를 출력한다. 소스코드. import sys from collections import deque def bfs(. turret1234.tistory.com 이 문제와 풀이가 똑 같다. 루트 노드와 가장 먼 노드를 구하고 그 노드와 가장 거리가 먼 노드와의 거리를 계산하여 출력한다. import sys from collections import deque def bfs(start): queue = deque() visited = [-1] * (n+1) que..
백준 1167 트리의 지름 - 파이썬 문제. 풀이. BFS를 이용하여 1번 노드와 가장 거리가 먼 노드를 구한다. 그리고나서 그 노드와 가장 거리가 먼 노드를 구하고 그 거리를 출력한다. 소스코드. import sys from collections import deque def bfs(start): queue = deque() visited = [-1] * (V+1) queue.append(start) visited[start] = 0 value = [0, 0] while queue: now = queue.popleft() for next, dist in graph[now]: if visited[next] == -1: visited[next] = visited[now] + dist queue.append(next) if value[0] < ..
백준 11725 트리의 부모 찾기 - 파이썬 문제. 풀이. 주어진 입력들을 양방향으로 연결하고 1에서 BFS를 실행하여 각 노드의 부모를 찾으면 된다. 소스코드. import sys from collections import deque def BFS(): answer = [0] * n visited = [False] * (n+1) queue = deque([1]) while queue: parent = queue.popleft() for i in tree[parent]: if not visited[i]: answer[i-1] = parent queue.append(i) visited[i] = True return answer[1:] input = sys.stdin.readline n = int(input()) tree = [[] for i in r..

티스토리툴바