개발자는 기록이 답이다

14. 그래프 최단거리(BFS) 예시 입력 1 6 9 1 3 1 4 2 1 2 5 3 4 4 5 4 6 6 2 6 5 예시 출력 1 2 : 3 3 : 1 4 : 1 5 : 2 6 : 2 1번 정점에서 각 정점으로 가는 최소 이동 간선수를 출력하세요. 1번 정점에서 2번정점을 간다고 하면 1->4->6->2 라서 총 3번이다. 1->3->4->6으로 갈 수 도 있지만 4번만에 가서 최단 간선수는 아니다. 1번은 0레벨이고, 1레벨만에 가는건 3,4번이라서 큐에 3,4번이 들어간다. 3,4는 1레벨이고 한번만에 간다는 의미이다. 이런식으로 레벨로 할 수 도 있다 1레벨 돌때, 큐에서 3,4가 나올텐데, for문 2바퀴 돌면서 탐색한다. 3에서 나올 수 있는건 4인데, 이미 체크된거라서 갈 필요 없다. 4에서..

9. 10. Tree 말단노드까지의 까장 짧은 경로(DFS/BFS) 루트노드에서 말단 노드까지 가는데 이동하는 횟수를 즉 간선(에지)의 개수를 구하라 이런 최단 거리 문제는 BFS로 풀어야 맞습니다. 하지만 배우기 위해 DFS로는 어떻게 풀어야하는지 알아보겠습니다. DFS는 제약이 있습니다. 3번 노드에서 자식노드가 6번 노드로 하나만 있을 경우 풀기 어렵습니다. 정확하게 2개 자식노드가 있거나 아예 없어야 합니다. BFS에서는 레벨 탐색이라 상관없습니다. DFS : Depth-First Search 0,1,2레벨이 있는데 한번만에 가는 1레벨은 말단 노드라면 3원소입니다. 레벨이 바로 문제에서 정의하는 이동 횟수(거처가는 간선의 횟수)를 말합니다. 말단 노드를 만났을때, 매개변수에 있는 root가 가르..

7. 이진트리 레벨탐색(BFS : Breadth-First Search) 이진트리 순회 (넓이 우선 탐색 : 레벨 탐색) 레벨 탐색 순회 출력 : 1 2 3 4 5 6 7 레벨 순으로 탐색합니다. 상태트리로 보자면, 루트 출발점에서 한번만에 갈 수 있는 노드들(간선)을 방문해보고, 2번만에 갈 수 있는 노드들 다 방문해보고 이런걸 BFS라고 합니다. 최단 거리 탐색에서 쓰인다. import java.util.LinkedList; import java.util.Queue; class Node { int data; Node lt, rt; public Node(int val) { data = val; lt=rt=null; } } public class Main { Node root; public void BF..