[Algorithms] BFS 코드 구조

 

 

public void bfs(Node root) {
	Queue<Node> q = new LinkedList<>();
	q.offer(root);

	while(!q.isEmpty()){
    
    	    // 현재 기준 Queue Size 만큼 Deque해서 처리
            for(int i=0; i<q.size(); i++){
                // dequeue
                Node curNode = q.poll();

                // [중요] 종료 조건 체크
                if(isTerminateCondition(curNode)){
                    return;
                }

                // 종료가 아니라면, find nextNode
                Node nextNode = makeCandidate(curNode);

                // enqueue
                if(checkAddCondition(nextNode) && !isVisit(nextNode)){
                    addVisitMap(nextNode); // [중요] enqueue할 때 visitMap에 추가한다!
                    q.offer(nextNode);
                }
            }
    }
}