[코테 알고리즘] BFS (Breadth First Search)

그래프의 모든 노드를 탐색하는 BFS(Breadth First Search)

---

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

시작노드에서 출발하여
레벨 기준으로 자기 레벨을 다 탐색하고
내려가는 과정을 반복하는 것을 ' 넓이우선탐색(BFS) '라고 한다.
** (시작노드 기준으로 가까운 노드를 먼저, 최단경로를 보장) **

🕑 시간복잡도: O(V+E) (V:정점수, E:간선수)
[모든 정점을 한 번씩 방문하고, 그러기 위해 모든 간선을 한 번씩 검사했으니]

BFS와 큐

---

BFS는 큐(Queue)로 구현하며,
큐(Queue)란 먼저 들어온게 먼저 빠지는 형태의 자료구조(FIFO)를 말한다

  Queue<Integer> queue = new ArrayDeque<>();

BFS 코드 구현

---

⚠️ 한번 방문한 노드를 다시 방문하면 안되므로, 방문여부를 체크할 배열(방문배열)이 필요하다.


** (보통 입력은 에지리스트로 주어지고, 이를 인접리스트로 바꿔 BFS구현한다) **

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * 백준 1260번 BFS
 * 
 * 입력:
 * 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 
 * 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 
 * 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
 *
 * 출력:
 * 첫째 줄에 BFS를 수행한 결과를
 * V부터 방문된 점을 순서대로 출력하면 된다.
 * 
 */
public class Main {
    static List<Integer>[] tree;
    static boolean[] isVisited;
    public static void BFS(int root) {
        Queue<Integer> queue = new ArrayDeque<>();
        isVisited[root] = true;
        // 루트노드를 queue에 넣는다
        queue.offer(root);
        // 큐가 빌때까지
        while(!queue.isEmpty()) {
            // 제일 앞단에 있는 요소를 꺼내서 출력
            int node = queue.remove();
            System.out.print(node + " ");
            // 인접노드를 하나씩 가져와
            for(int adj : tree[node]) {
                if(isVisited[adj]) continue;
                isVisited[adj] = true;
                // 큐에 넣어준다
                queue.offer(adj);
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(br.readLine(), " ");
        // 정점의 개수 N
        int N = Integer.parseInt(token.nextToken());
        // 간선의 개수 M
        int M = Integer.parseInt(token.nextToken());
        // 시작정점 번호 V
        int V = Integer.parseInt(token.nextToken());

        // 인덱스0은 쓰지 않고 1부터 N까지 인덱스 사용
        tree = new ArrayList[N+1];
        isVisited = new boolean[N+1];

        // 배열의 각 요소를 ArrayList로 초기화
        for(int i = 0; i < tree.length; i++) {
            tree[i] = new ArrayList<>();
        }

        // 간선의 개수만큼 입력받는다
        for(int i = 0; i < M; i++) {
            token = new StringTokenizer(br.readLine(), " ");
            int u = Integer.parseInt(token.nextToken());
            int v = Integer.parseInt(token.nextToken());
            tree[u].add(v);
        }

        // test 출력
//        for(int i = 0; i < tree.length; i++) {
//            System.out.println(i +": " + tree[i]);
//        }
        BFS(V);
    }
}