그래프8 [백준] 11725번 : 트리의 부모 찾기 – JAVA [자바] https://www.acmicpc.net/problem/11725 문제 해결 방법이 문제는 루트 없는 트리에서 각 노드의 부모를 찾는 문제이다. BFS(너비 우선 탐색) 또는 DFS(깊이 우선 탐색)을 활용하여 해결할 수 있다.1. 그래프 구성입력으로 주어진 트리의 연결 정보를 이용하여 인접 리스트를 만든다.각 노드는 서로 연결된 상태이며, 양방향 간선으로 주어진다.2. BFS를 이용한 부모 노드 찾기BFS(너비 우선 탐색) 방법을 사용한다.루트 노드(1번 노드)부터 탐색을 시작하며, 자식 노드들의 부모를 기록한다.방문한 노드는 다시 방문하지 않도록 한다.3. 결과 출력2번 노드부터 N번 노드까지의 부모를 순서대로 출력한다. 코드 import java.io.*;import java.util.*.. 2025. 3. 25. [백준] 16953번 : A → B – JAVA [자바] https://www.acmicpc.net/problem/16953 문제 해결 방법이 문제는 BFS(너비 우선 탐색) 를 활용하여 해결할 수 있다. BFS는 최단 경로를 찾는 데 유용한 알고리즘이기 때문에, 최소 연산 횟수를 구하는 데 적합하기 때문이다. 만약에 다른 방법을 이용해서 이 문제를 풀었다면 댓글로 공유해주기 바란다. 1. 큐 (Queue)를 활용하여 탐색을 진행한다.2. 시작 값 A를 큐에 넣고, 연산을 수행하며 다음 숫자들을 큐에 추가한다. 다음 숫자들은 2를 곱한 숫자나 뒷자리에 1을 추가한 숫자를 뜻한다.3. 새로운 숫자가 B보다 작다면 계속 진행하고, B와 같다면 연산 횟수를 출력하고 종료한다. 새로운 숫자가 B보다 크면 B가 절대로 될 수 없다 (새로운 숫자는 2를 곱한 값이나 .. 2025. 3. 10. [알고리즘] DFS & BFS 목차 DFS (깊이 우선 탐색) DFS (Depth-First Search)는 깊이 우선 탐색이라고도 하며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 재귀나 스택을 이용해서 구현을 한다. DFS를 구현할 때 어떤 노드를 방문했었는지 꼭 검사를 해야 한다. 왜냐하면 이를 검사하지 않을 경우 무한루프에 빠질 수 있기 때문이다. 보통 모든 노드를 방문하고자 할 때, DFS를 이용한다. 하지만, 검색 속도는 보통 BFS보다 느리다. 구현 방법 : 1. 탐색 시작 노드를 스택에 삽입하고, 방문 처리한다. 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리하고, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3. 위의 1번.. 2022. 5. 23. [알고리즘] 플로이드 와샬 (Floyd Warshall) 목차 플로이드 와샬이란? 다익스트라 알고리즘은 하나의 노드에서 출발했을 때 다른 모든 노드로의 최단 경로를 구하는 알고리즘이다. 하지만 플로이드 와샬 알고리즘은 모든 노드에서 모든 노드로의 최단 경로를 구하는 알고리즘이다. 그리고 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택을 해서 그 적은 비용을 가지는 노드의 인접한 노드들로 가는 비용을 하나씩 계산하는 방식이었다면 플로이드 와샬 같은 경우는 거쳐가는 노드를 기준으로 알고리즘을 수행한다는 특징이 있다. 추가로 플로이드 와샬은 다이나믹 프로그래밍 기법을 사용한 알고리즘이고, 인접 행렬을 이용하여 각 노드 간 최소의 비용을 계산한다. 플로이드 와샬 예시 위와 같은 그래프가 있다고 가정해 보겠다. 그리고 각각의 노드에서 다른 노드로 가는 비용을 2차원.. 2022. 5. 21. 이전 1 2 다음 반응형
