코딩테스트 및 알고리즘41 BFS 응용 문제. 현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요. 입력 예시 5 14 답 : 3 나의 답변 public class Main { int[] dis = {-1,1,5}; int[] ck; public int BFS(int s, int e) { ck = new int[10001]; ck[s] = 1; Queue q = .. 2024. 2. 24. BFS(큐 사용) 이진 트리 순회( 넓이 우선 탐색 ) 레벨순회 : 1 - 2 - 3 - 4 - 5 - 6 - 7 출발점에서 특정 조건을 가진 Node로 가는 최단거리를 구하는데 유용하다. 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 BFS(Node root) { Queue Q = new LinkedList(); Q.offer(root); int Level = 0; while(!Q.isEmpty()) { int len=Q.size(); System... 2024. 2. 23. DFS 부분 집합 구하기 문제 . 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 구하시오. (공집합 제외) 입력 예시 3 답 : 1 2 3 1 2 1 3 1 2 3 2 3 나의 답변 public class Main { static int n; static int[] ch; public void DFS(int L) { if(L==n+1) { // 모든 원소를 선택한 경우 String tmp=""; for(int i=1; i0) System.out.println(tmp); }else { // 현재 위치의 원소를 선택한 경우 ch[L]=1; // 다음 위치로 이동하여 재귀적으로 탐색 DFS(L+1); // 현재 위치의 원소를 선택하지 않은 경우 ch[L]=0; // 다음 위치로 이동하여 재귀적으로 탐색 DF.. 2024. 2. 21. DFS 이진 트리 순회( 깊이 우선 탐색 ) 전위순회 : 부모를 제일 먼저 방문 ( 부모 - 왼쪽자식 -오른쪽 자식 ) / 1 - 2 - 4 - 5 - 3 - 6 - 7 중위순회 : 부모를 중간에 방문 ( 부모 - 왼쪽자식 -오른쪽 자식 ) / 4 - 2 - 5 - 1 - 6 - 3 - 7 후위순회 : 부모를 가장 나중에 방문 ( 왼쪽자식 -오른쪽 자식 - 부모 ) / 4 - 5 - 2 - 6 - 7 - 3 - 1 // 이진 트리의 노드 class Node{ int data; Node lt, rt; // Node 객체 주소 저장 public Node(int val){ data=val; lt=rt=null; } } public class Main { Node root; public void DFS(Node roo.. 2024. 2. 20. 이전 1 2 3 4 5 ··· 11 다음
