BFS2 [JAVA] 너비 우선 탐색 (BFS) 너비 우선 탐색은 시작 정점에 인접한 정점들을 모두 방문한 뒤에 이 정점들에 인접한 방문하지 않은 정점들을 모두 방문한다. 이 과정을 반복해 정점들을 시작 정점까지의 최단 경로의 길이 순서대로 방문한다. 만약 탐색이 종료된 후에 아직 방문하지 않은 정점들이 남아 있다면 그 정점들 중 한 정점에서 너비 우선 탐색을 시작한다. 너비 우선 탐색 알고리즘은 깊이 우선 탐색과 달리 재귀를 사용하여 작성할 수 없는 유형이다. 대신 너비 우선 탐색은 큐를 사용하여 쉽게 작성할 수 있다. 시간복잡도 - 인접 리스트: O(V+E) - 인접 행렬: O(V^2) 알고리즘 알고리즘 BFSearch(G) 1 V에 있는 각 정점을 '방문 안함'으로 표시한다 2 각 정점 v에 대해 v가 '방문 안함'으로 표시되어 있다면 BFS(v.. 2021. 12. 14. [JAVA] 2178번 미로 탐색 문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 최소칸 수를 구하는 문제에는 bfs를 사용해 푸는 것이 더 효율적이다. bfs 알고리즘을 적용하여 간단히 문제를 풀이하였다. import java.awt.Point; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringT.. 2021. 9. 21. 이전 1 다음