728x90 알고리즘339 [Python] 백준 1991 트리 순회 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 문제 해결 전위 순회(preorder) 중위 순회(inorder) 후위 순회(postorder) 스캔 순서 노드 방문→왼쪽 자식→오른쪽 자식 왼쪽 자식→노드방문→오른쪽 자식 왼쪽 자식→오른쪽 자식 →노드 방문 예시 A→B→D→C→E→F→G D→B→A→E→C→F→G D→B→E→G→F→C→A 위 내용을 잘 모르겠으면 자료구조(Data Structure)의 트리 부분을 공부하고 오는 것이 좋.. 2022. 12. 10. [Python] 백준 1967 트리의 지름 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제 해결 - 간선에 가중치(거리)가 있다. - 부모 자식 관계는 중요하지 않다. 그냥 노드와 노드사이의 가중치 합이 큰 것을 찾아야 한다. - 제일 위에 있는 1에서 시작해서 가장 멀리 있는 것을 찾아본다. 이거는 BFS나 DFS 둘다 가능할 것이다. - 가장 멀리 있는 인덱스에서 다시 시작해서 가장 멀리 있는 노드까지 가중치(거리) 합을 구한다. 이 것이 정답. - 유사문제.. 2022. 12. 10. [Python]백준 1167 트리의 지름 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 해결 - graph 리스트를 통해 연결되어있는 점들의 정보를 저장한다. - visited[i] = value : 1점에서 i점까지 거리가 value인 것을 나타낸다. - 어느 점에서 시작하든 반대쪽 리프(맨 밑에 있는점)까지가 가장 멀기 때문에 한 점에서 가장 멀리 떨어져 있는 점을 구한다. visited.index(max(visited))를 통해 구한다. - 1점에서 반대쪽.. 2022. 12. 10. 이전 1 ··· 82 83 84 85 다음 728x90
