728x90 반응형 BFS2 Tree : Top View 이진 트리의 "상단 뷰"를 찾는 문제입니다. 상단 뷰란 이진 트리를 위에서 아래로 내려다 볼 때, 가장 왼쪽 노드부터 가장 오른쪽 노드까지 순서대로 보이는 노드들의 값을 출력하는 것을 의미합니다. 상단 뷰를 찾기 위해서는 이진 트리의 루트 노드에서 시작하여 왼쪽으로 이동할 때는 왼쪽 자식 노드로, 오른쪽으로 이동할 때는 오른쪽 자식 노드로 이동하면서 노드들의 값을 출력해야 합니다. 이 때, 같은 수평 레벨에 여러 노드가 있는 경우에는 가장 왼쪽 노드를 출력해야 합니다. 문제의 목표는 주어진 이진 트리에서 상단 뷰에 있는 노드들의 값을 순서대로 출력하는 것 BFS(Breadth-First Search) 알고리즘을 사용하여 풀 수 있습니다. BFS를 사용하면 각 노드의 수평 거리를 추적할 수 있으며, 각 수.. 2023. 10. 5. BFS와 DFS 너비 우선 탐색(BFS , Breadth-First Search) 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 사용하는 경우 : 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 선택 ex) A,B사이에 존재하는 경로를 찾는 경우, A에서 가까운 곳 부터 탐색 그래프 탐색의 경우, 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. -> 이를 검사하지 않을 경우, 무한루프에 빠질 위험이 있다. BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐를 사용한다. ->프림과 다익스트라 알고리즘과 유사하다. BFS(G,k) q.push(G.root) root.visit = true while !q.isEmpty() node r = q.fron.. 2019. 5. 2. 이전 1 다음 728x90 반응형