개발자는 기록이 답이다

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

8. 송아지 찾기1(BFS) 예시 입력 1 5 14 예시 출력 1 3 이전에 찾았던건 무시해줍니다. 최초로 발견되는게 최단거리 입니다. 14까지 3번만에 갈 수 있다는 것입니다 5 -> 4 -> 9 -> 14 이런걸 상태 트리라고 합니다. 3레벨 탐색하니까 14번을 발견하고 루트에서 몇번만에 갔는지를 출력하면 됩니다. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; // 최단 거리 구하기 public class Main { int answer = 0; // 최소 횟수 카운팅 int[] dis = {1, -1, 5}; // 앞으로 전진, 뒤로 후진, 5칸 앞으로 전진 int[] ch; // 체크 배열 : 한 번 방..

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..

6. 부분집합 구하기(DFS) 단, 공집합은 출력하지 않습니다. 예시 입력 1 3 예시 출력 1 1 2 3 1 2 1 3 1 2 3 2 3 3은 1,2,3이 집합의 원소입니다. 부분집합은 2의 3제곱해서 8개 인데, 공집합 배니까 7개만 출력됩니다. 이진 트리로 2 갈래로 뽑는 상태 트리를 만들면 됩니다. 어떤 상태를 표현하는 트리를 상태 트리라고 합니다. {1,2,3} 집합이 있을때 원소를 뽑아내서 부분집합을 만들어 내려고 할때, 1을 넣을 수도 있고 넣지 않을 수도 있습니다. 2를 넣을 수도 있고 넣지 않을 수도 있습니다. 3을 넣을 수도 있고 넣지 않을 수도 있습니다. 숫자 하나 당 2가지 경우가 존재합니다. 이렇게 곱하면 총 8가지입니다. 원소가 n개인 집합의 개수는 2의 n제곱이다. - 공집합도..