BFS 2

[백준 *Java] - 4연산(14395)

4연산 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net 문제 정수 s가 주어진다. 정수 s의 값을 t로 바꾸는 최소 연산 횟수를 구하는 프로그램을 작성하시오. 사용할 수 있는 연산은 아래와 같다. s = s + s; (출력: +) s = s - s; (출력: -) s = s * s; (출력: *) s = s / s; (출력: /) (s가 0이 아닐때만 사용 가능) 입력 첫째 줄에 s와 t가 주어진다. (1 ≤ s, t ≤ 109) 출력 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 ..

PS/백준 2022.06.03

너비 우선 탐색(Breadth-First-Search)

BFS 그래프 전체를 탐색하는 방법 중 하나로, 루트 노드 또는 다른 임의의 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법입니다. 시작 정점을부터 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 순회함으로 써 노드를 넓게(wide)하게 탐색을 합니다. 더 설명하자면, BFS는 해를 찾아서 조직적으로 트리의 모든 노드들을 검사하는 무정보 탐색(Uniformed search)입니다. 달리 말하자면, 목표에 대한 고려없이 목표가 발견될 때까지 전체 트리 또는 그래프를 전부 탐색하고, BFS는 휴리스틱을 사용하지 않습니다. (반대로 휴리스틱을 사용하는 알고리즘은 ex) Greedy best-first search 또는 A*) 👇 search 의 두 분류 더보기 Uniformed search ..