[탐색] BFS(너비 우선 탐색)

📌 BFS(Breadth-First-Search)

⭐ 개념

• 루트 노드 또는 임의 노드에서 인접한 노드부터 먼저 탐색하는 방법
• 최소 비용(즉, 모든 곳을 탐색하는 것보다 최소 비용이 우선일 때)에 적합
• Queue 구조
• FIFO

✅ 시간복잡도

• 인접 행렬 : O(V^2)
• 인접 리스트 : O(V+E)

⭐ 로직

1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
2. 큐에서 노드를 꺼낸 후 꺼낸노드의 인접노드를 다시 큐에 삽입하기
3. 큐 자료구조에 값이 없을 때까지 반복

⭐ 코드

static ArrayList<Integer>[] A;
static boolean visited[];

public static void main(String[] args){
	A = new ArrayList[N+1];
	visited = new boolean[N+1];
	
	for(int i=0; i<=N; i++) {
		A[i] = new ArrayList();
	}
	
    // 간선 배열 만들기
	for(int i=0; i<M; i++) {
		int start = sc.nextInt();
		int end = sc.nextInt();
		A[start].add(end);
		A[end].add(start);
	}
	BFS(1);
}

public static void BFS(int Node) {
	Queue<Integer> queue = new LinkedList<>();
	visited[Node] = true;
	queue.add(Node);
	while(!queue.isEmpty()) {
		Node = queue.peek();
		for(int i : A[Node]) {
			if(!visited[i]) {
				queue.add(i);
				visited[i] = true;
			}
		}
		System.out.print(queue.poll() + " ");					
	}
}