BFS 공부

BFS(너비 우선 탐색)은 깊이가 작은 노드부터 차례대로 방문하는 전체 탐색 방식이라고 말할 수 있다.

보통 BFS는 큐로 많이 풀게 되는데, queue를 이용하여 문제를 푸는 순서는 다음과 같다.

1. queue의 가장 앞에 있는 노드 pop

2. 현재 노드에 인접한 모드 노드 중 아직 방문하지 않은 노드를 queue에 push

3. queue 가 비어있지 않으면, 1번부터 다시 실행

큐의 작동원리를 알고 계신다면, 깊이가 낮은 순서대로 탐색하는 것을 이해하실 수 있으실 겁니다 :)

위의 논리구조로 코드를 구현하게 된다면,

queue에 방문 node offer();

방문 배열[노드] = true;

while(!queue.isEmpty()){

v = q.poll();

if(v와 인접한 노드 && 미방문 노드){

queue에 offer();

방문배열[추가노드] = true;

}

}

더 이상 Queue에 남아있는 정점이 없을 때, 혹은 답을 찾게되면 탐색을 종료한다. 

BFS의 깊이를 구해야한다면, 사용하는 Queue에 -9999(dummy value)를 넣고, -9999를 만나면 depth level을 증가한다.

그러나 연속적으로 dummy value를 만나게 된다면 이는 모든 노드를 탐색한 경우이므로 while 문을 빠져나온다.

논리구조 코드는 다음과 같다.

queue.offer(root);

queue.offer(-9999);

while(!queue.isEmpty()){

cur = queue.poll();

if(cur == -9999){

level++;

queue.offer(-9999);

if(queue.peek() == -9999){ break; }

}

...(생략)

}