[알골90제] 69번 - 넓이우선탐색 BFS (큐 자료구조 구현)

이진트리 넓이 우선 탐색

 

* 넓이우선 탐색이란? BFS = level 탐색

1번 노드를 탐색한다 - 1 level

1번 노드에서 1번만에 갈 수 있는 모두를 방문한다. - 2 level

1번 노드에서 2번만에 갈 수 있는 모두를 방문한다. - 3 level

 

1 2 3 4 5 6 7

 

 

* 레벨 탐색 할때 QUEUE 큐라는 자료구조를 사용한다.

https://gmlwjd9405.github.io/2018/08/02/data-structure-queue.html

[자료구조] 큐(Queue)란 - Heee's Development Blog

-큐는 먼저 들어간 것이 먼저 나오는 것 FIFO - First In First Out

- f 는 front 

- b 는 back

 

처음에는 f = -1, b = -1 한다.

처음 들어갈 때, b ++;

b가 가리키는 자리에 1번 노드 값 넣기

 

꺼낼 때 , f++

1번 노드와 연결되어 있는 노드들 탐색하여 큐에 다 넣기

2와 3 두 자료를 큐에 넣는다. 이때 b++계속 됨

 

꺼낼때 다시  f++ 하고  2가 나옴

 

출력한 자료와 연결되어 있는 노드들을 다시 탐색한다. => 큐에 다시 넣는다.

 

=> 1번에서 가장 가까운 것 방문하고 그 다음으로 가까운 것 방문하고....

 

 

// 69번 - 넓이우선탐색 BFS (큐 자료구조 구현)
// 무방향 그래프리스트

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int Q[100], front = -1, back = -1, ch[10];
vector<int> map[10];

int main() {

	int a, b, x;
	
	for (int i = 1; i <= 6; i++) {
		scanf("%d %d", &a, &b);
		map[a].push_back(b); //인접리스트 만듬
		map[b].push_back(a); //무방향이라 이 코드도 추가
	}

	//큐 운영
	Q[++back] = 1; // 큐에 1번 루트 노드 넣기
	ch[1] = 1; // check 배열에 1 넣기

	while (front < back) { //같아지는 순간 queue는 비어있다는 것
		x = Q[++front]; //빼는거
		printf("%d", x); //빼고 출력

		for (int i = 0; i < map[x].size(); i++) {
			if (ch[map[x][i]] == 0) {
				ch[map[x][i]] = 1;
				Q[++back] = map[x][i];
			}
		}
	}
	return 0;
}