BFS . 5

✅🌲강의 복습 노트/이코테2021 알고리즘 훈련

BFS . 5

들판속초록풀 2024. 11. 3. 23:57

BFS 구현 방법 : 1. Queue 로 구현

BFS (Breadth-First-Search) : 너비 우선 탐색 , 그래프에서 가까운 부분을 우선적으로 탐색하는 알고리즘 , 그래프 탐색

사용한 자료들 : 큐 , visited 배열 , 그래프 (ArrayList 클래스)

BFS 유형은 최단 거리 유형의 문제에 활용되기도 한다

모든 작업이 끝나면 큐 안은 비워져 있다.

import java.util.*;

public class Main {
    public static boolean[] visited = new boolean[9];           // Main 클래스의 멤버변수
    public static List<List<Integer>> graph = new ArrayList<>();

    public static void main(String[] args) {
                                               // 초기화 (0번 인덱스는 사용하지 않음)
        for (int i = 0; i < 9; i++) {
            graph.add(new ArrayList<>());
        }

                                                        // 초기화 (간선 정보 추가)
        graph.get(1).addAll(Arrays.asList(2, 3, 8));
        graph.get(2).addAll(Arrays.asList(1, 7));
        graph.get(3).addAll(Arrays.asList(1, 4, 5));
        graph.get(4).addAll(Arrays.asList(3, 5));
        graph.get(5).addAll(Arrays.asList(3, 4));
        graph.get(6).addAll(Arrays.asList(7));
        graph.get(7).addAll(Arrays.asList(2, 6, 8));
        graph.get(8).addAll(Arrays.asList(1, 7));

                                       // 각 리스트 정렬 (번호가 낮은 노드를 우선 방문하기 위함)
        for (int i = 1; i <= 8; i++) {
            Collections.sort(graph.get(i));
        }

        bfs(1);        // BFS 실행 
    }

    // BFS 함수 정의
    public static void bfs(int start) {  // 인스턴스 생성해서 호출하지 않고 static인 main메서드에서 바로 사용 가능하게 static으로 선언함 
        Queue<Integer> q = new LinkedList<>();      // Queue 사용 : LinkedList 클래스 사용
        q.offer(start);
        visited[start] = true;

        while (!q.isEmpty()) {
            int current = q.poll();               // 큐에서 삭제하면서 반환
            System.out.print(current + " ");      // 가로출력을 하기 위해 print 로 출력

            for (int neighbor : graph.get(current)) {   // 향상된 for문
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.offer(neighbor);
                }
            }
        }
    }
}

BFS 코드 예제 : DFS 와 마찬가지로 BFS 도 0번 인덱스를 비워두고, visited 배열의 요소를 9개로 선언한다

파이썬 예제

queue = deque([start]) # 시작 노드를 큐에 넣어준다
파이썬 deque 를 출력해보면 deque([1,2]) 이런 형태로 출력이 된다.
(큐의 요소 하나가 리스트 하나인 느낌)

while queue # 큐가 참일 때 --> 큐가 0이 아닐 때 --> 큐가 비어있지 않을 때

(popleft 함수는 반환까지 하는 함수인듯)