BFS2 [백준] 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. 이전 1 다음 반응형
