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

HSRyuuu dev blog·2023년 4월 3일

algorithm

Algorithm

목록 보기

2/4

BFS(Breadth-First Search) : 깊이 우선 탐색

그래프 완전 탐색
시작 노드에서 출발해 시작 노드를 기준으로 가장 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.
FIFO 탐색 -> Queue 자료구조를 이용한다.
목표 노드에 도착하는 경로가 여러개일 때 최단경로를 보장한다.

1. 시간복잡도

시간복잡도(노드 수: N, 에지 수 E)

O(N+E)

2. BFS 핵심 이론

1) 방문여부 확인용 배열

1	2	3	4	5	6
T	F	F	F	F	F

BFS도 DFS와 마찬가지로 한번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 배열이 필요하다.
예를들어 1~6의 노드를 가진 그래프가 있으면, boolean[] arr = new boolean[7]; 으로 배열을 만들어 준다.( 0번 인덱스는 사용하지 않는다. )
해당 노드를 방문하면 해당 인덱스의 값을 TRUE로 바꿔준다.

2) 원본 그래프 -> 자료구조 초기화(인접리스트)

시작할 노드를 정한다.
각 노드에서 갈수있는 다른 노드를 확인 후 인접리스트로 초기화 한다.
시작점을 정했기 때문에 시작점의 방문배열을 T로바꿔주고, Queue에 시작점을 더한다.

3) Queue에서 노드를 꺼낸 노드의 인접노드를 Queue에 삽입

맨 처음에 넣었던 노드1을 Queue에서 꺼낸다.
꺼낸 노드 1의 인접노드(2,3)을 큐에 삽입한다.
이 과정을 Queue가 비워질 때까지 반복한다.

4) 반복

(편의를 위해 poll() 괄호 안에 값을 넣도록 하겠다.)
1. 위에서 1을 꺼낸 뒤, 노드2,3을 넣은 상태이다.

2. poll(2) -> 2의 방문배열 True -> 2의 인접 리스트 5,6을 넣는다. offer(5), offer(6)

3. poll(3) -> 3의 방문배열 True -> 3의 인접 리스트 4를 넣는다. offer(4)

4. poll(5) -> 5의 방문배열 True -> 5의 인접리스트는 없다.

5. poll(6) -> 6의 방문배열 True -> 6의 인접리스트는 없다.

6. poll(4) -> 4의 방문배열 True -> 4의 인접리스트는 없다.

7. queue.isEmpty() == true

3. 구현

    static boolean[] visited = new boolean[7]; //방문 배열 초기화
    static Queue<Integer> queue = new LinkedList<>();
    static ArrayList<Integer>[] A = new ArrayList[7]; //ArrayList 타입 배열 선언
    static ArrayList<Integer> procedure = new ArrayList<>(); //탐색 순서 출력을 위한 리스트

    public static void main(String[] args){
        //ArrayList 형 배열 A 초기화
        for(int i=1;i<=6;i++) {
            A[i] = new ArrayList<>();//배열의 각 요소마다 ArrayList를 가진다.
        }
        //위의 예제 인접 리스트 초기화
        A[1].add(2);
        A[1].add(3);
        A[2].add(5);
        A[2].add(6);
        A[3].add(4);
        A[4].add(6);

        BFS(1);
        
        System.out.println(procedure.toString()); //[1, 2, 3, 5, 6, 4]
    }
    private static void BFS(int start){
        queue.offer(start);
		
        while(!queue.isEmpty()){
            int now = queue.poll();
            // poll() 할때, 탐색순서 리스트에 넣어주고,방문배열을 true로 바꿔준다.
            procedure.add(now); 
            visited[now] = true;

            // 꺼낸 노드의 인접노드를 전부 확인한다.
            for(int i=0;i<A[now].size();i++){
                int node = A[now].get(i);

                //인접노드가 방문한적 없는 노드면 queue에 넣어준다.
                if(!visited[node]){
                    queue.offer(node);
                }
            }
        }//while문
    }//BFS 메소드
    
}