[BFS 정의 구현 코드]

[bombo-dev]

자바 BFS 구현 시 코드가 다음으로 되어있습니다.
Queue q = new Queue<>();

자바에서 일반적인 자료구조 Queue의 구현은 다음과 같습니다.
Queue q = new LinkedList<>();

교재는 파이썬 기반이므로 deque를 사용하고 있고, deque 기반으로 코드가 진행되고 있습니다.
하지만 자바에도 ArrayDeque가 있습니다. 이는 파이썬 deque와 비슷합니다.

ArrayDeque q = new ArrayDeque<>();

Queue 인터페이스를 구현했기 때문에 Queue가 제공하는 add, offer, remove, poll은 기본적으로 사용이 가능합니다.
추가적으로 python의 deque.popleft()와 동일하게 자바에서는 다음과 같이 제공합니다.
q.pollFirst();

ArrayDeque의 소스코드를 확인해보시면 다음과 같이 양방향 큐를 이용하기 위해 다음과 같은 메소드가 있습니다.
addFirst(), addLast(), offerFirst(), offerLast()
removeFirst(), removeLast(), pollFirst(), pollLast()

공부하시는데 참고가 되었으면 하고 코드를 이와 같이 업데이트를 해도 좋을 것 같습니다.

import java.util.*;

public class Main {
    public static boolean[] visited = new boolean[9];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

    public static void bfs(int start){
        ArrayDeque<Integer> q = new ArrayDeque<>(); // new LinkedList<>();
        q.offer(start);
        visited[start] = true;

        while(!q.isEmpty()){
            Integer x = q.pollFirst();
            for(int i = 0; i < graph.get(x).size(); i++){
                int y = graph.get(x).get(i);
                if(!visited[y]){
                    q.offer(y);
                    visited[y] = true;
                }
            }
        }
    }
}