알고리즘 문제풀이 입문: 코딩테스트 대비/섹션 7. Recursive, Tree, Graph(DFS,BFS 기초)9 송아지 찾기1 (BFS) 설명현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다.현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다.송아지는 움직이지 않고 제자리에 있다.현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다.최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요. 입력첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000까지이다. 출력점프의 최소횟수를 구한다. 답은 1이상이며 반드시 존재합니다. 예시 입력 1 5 14 예시 출력 13 문제 해결 최단 거리 문제이므로 BFS를 사용하는 게 적합.. 2024. 5. 9. 그래프 최단거리(BFS) 설명다음 그래프에서 1번 정점에서 각 정점으로 가는 최소 이동 간선 수를 출력하세요. 입력첫 번째 줄에 정점의 수 N(1 출력1번 정점에서 각 정점으로 가는 최소 간선 수를 2번 정점부터 차례대로 출력하세요. 예시 입력 1 6 91 31 42 12 53 44 54 66 26 5 예시 출력 12 : 33 : 14 : 15 : 26 : 2 문제 해결 최단 거리이므로 BFS로 해결해보자.1에서 시작하기때문에 1은 03과 4 => 1 (한 번만에 갈 수 있으므로). 그리고 1,3,4는 큐에 들어간 상태이며 방문했다고 체크3이 큐에서 나오고 연결된 4. 4는 이미 체크됐으므로 4에서 연결된 5,6을 체크.5는 4의 값에 +1 (dis[nv] = dis[v] +1) 즉 2 그리고 큐에 들어가고 체크6도 2, 큐에 .. 2024. 5. 9. 경로탐색 (인접 행렬 / 인접 리스트) 설명방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 1 2 3 4 51 2 51 3 4 2 51 3 4 51 4 2 51 4 5총 6가지입니다. 입력첫 번째 줄에 정점의 수 N(1 출력총 가지수를 출력한다. 예시 입력 1 5 91 21 31 42 12 32 53 44 24 5 예시 출력 16 문제 해결 1번 정점에서 시작하여 N번 정점으로 가는 모든 경로의 수를 찾는 문제이므로 DFS를 이용해 모든 경로를 탐색할 수 있다.각 정점을 방문할 때마다 방문했다는 표시를 해두고, 탐색을 마친 후에는 그 표시를 지워 다른 경로에서 해당 정점을 다시 방문할 수 있게 해야 하는 것이 포인트이.. 2024. 5. 9. Tree 말단 노드까지 가장 짧은 경로 (DFS, BFS) 설명아래 그림과 같은 이진 트리에서 루트 노드 1에서 말단 노드까지의 길이 중 가장 짧은 길이를 구하는 프로그램을 작성하시오. 각 경로의 길이는 루트 노드에서 말단 노드까지 가는데 이동하는 횟수를, 즉 간선의 개수를 길이로 한다. 가장 짧은 길이는 3번 노드까지의 길이인 1이다 문제 해결 사실 이 문제는 최단 거리를 구하는 문제이므로 DFS 보다는 BFS 가 더 적합하다. 연습을 위해 둘 다 풀어보라는 취지같다. DFS를 이용하려면 루트 노드부터 시작해 말단 노드에 도달하면 현재 깊이를 반환하고, 부모 노드로 돌아가서 다시 다른 경로를 탐색하고 깊이를 반환하고....의 과정이다. 이를 통해 가장 짧은 길이를 찾으면 된다.public static int DFS(int L, Node root) { .. 2024. 5. 8. 이진트리 레벨탐색 (BFS : Breadth-First Search) 설명아래 그림과 같은 이진트리를 레벨탐색 연습하세요. 레벨 탐색 순회 출력 : 1 2 3 4 5 6 7 문제 해결 레벨 탐색은 말 그대로 레벨 별로 탐색하는 것이다.루트에서 한 번만에 갈 수 있는 애들을 모두 방문하고, 두 번만에 갈 수 있는 애들을 방문하고 ... 이런 식의 과정이다. BFS의 핵심은 큐를 이용하는 것이다. (Queue => FIFO 구조)이전에 이진트리를 구성했던 방법대로 위 문제 사진과 같이 이진트리를 만들어준다static Node root;public static void main(String[] args) { root = new Node(1); root.lt = new Node(2); root.rt = new Node(3); root.lt.lt = new.. 2024. 5. 7. 부분집합 구하기 (DFS) 설명자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요. 입력첫 번째 줄에 자연수 N(1 출력첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래와 출력예제와 같은 순서로 출력한다.단 공집합은 출력하지 않습니다. 예시 입력 1 3 예시 출력 11 2 31 21 312 323 문제 해결 부분집합을 출력하는 문제이다.1 2 3 이 있으면 1을 2를 3을 부분집합에 넣을 수도 있고, 안 넣을 수도 있다.=> 각각 경우의 수가 2가지 (즉 2의 n제곱)예제 입력 3은 2의 3제곱 8개인데 공집합을 제외하니 7개의 부분집합이 나온다. static int[] ch; 사용 여부를 체크할 체크 배열을 N+1 크기로 선언해준다. DFS(1)이 호출되고, 첫 번째 숫자(1)를.. 2024. 4. 30. 이전 1 2 다음 반응형
