[알고리즘] BFS 너비 우선 탐색

BFS란?

가까운 노드부터 탐색. 즉 옆에 있는 것부터 탐색.
큐를 이용하여 구현.

BFS 방법

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리.
2. 큐에서 노드를 꺼내 인접 노드 중 방문하지 않은 노드 모두 큐에 삽입하고 방문처리.
3. 2번을 처리할 수 없을 때 까지 실행.

public class BFS {

    public static void Solution(int[][] graph) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[graph.length];
        queue.add(1); // START
        visited[1] = true;
        while (!queue.isEmpty()) {
            int num = queue.poll();
            System.out.println(num);
            for (int i = 0; i < graph[num].length; i++) {
                if (!visited[graph[num][i]]) {
                    queue.add(graph[num][i]);
                    visited[graph[num][i]] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[][] graph = {{},
                {2, 3, 8}, // 1번 노드와 연결된 노드들
                {1, 7}, // 2번 노드와 연결된 노드들
                {1, 4, 5},
                {3, 5},
                {3, 4},
                {7},
                {2, 6, 8},
                {1, 7}};
        Solution(graph);
    }
    
}